Что такое алгоритм сортировки?

Алгоритм сортировки - это алгоритм, который размещает элементы списка в определенном порядке. Наиболее часто используемые порядки - это числовой и лексикографический порядок.
Эффективная сортировка важна для оптимизации эффективности других алгоритмов, которые требуют, чтобы входные данные были в отсортированных списках.

Список наиболее часто используемых алгоритмов сортировки

Основные алгоритмы сортировки:

  1. Пузырьковая сортировка
  2. Выбор Сортировка
  3. Вставка сортировки
  4. Сортировка кучи
  5. Сортировка слиянием
  6. Быстрая сортировка

Алгоритмы предварительной сортировки:

  1. Радиксная сортировка

Пузырьковая сортировка:

Пузырьковая сортировка - это алгоритм, основанный на сравнении, который сравнивает каждую пару элементов в массиве и меняет их местами, если они не в порядке, пока не будет отсортирован весь массив. Для каждого элемента в списке алгоритм сравнивает каждую пару элементов.

Псевдокод:

swapped = true
  while swapped
      swapped = false
      for j from 0 to N - 1
         if a[j] > a[j + 1]
            swap( a[j], a[j + 1] )
            swapped = true

Сортировка выделения:

Сортировка по выбору - это алгоритм на основе сравнения на месте, который разделил список на две части: отсортированную часть слева и несортированную часть справа. Изначально отсортированная часть пуста, а неотсортированная часть представляет собой весь список.
Наименьший элемент выбирается из несортированного массива и заменяется крайним левым элементом, и этот элемент становится частью отсортированного массива. Этот процесс продолжает перемещать границу несортированного массива на один элемент вправо.

Псевдокод:

func selsrtI(lst)
  	max = length(lst) - 1

 	 for i from 0 to max
      	key = lst[i]
      	keyj = i

      	for j from i+1 to max
          	if lst[j] < key
              		key = lst[j]
              		keyj = j

     	 lst[keyj] = lst[i]
     	 lst[i] = key

 	 return lst
 end func

Сортировка вставкой:

Сортировка вставкой - это алгоритм, основанный на сравнении, который строит окончательный отсортированный массив по одному элементу за раз. Он выполняет итерацию по входному массиву и удаляет один элемент за итерацию, находит место, которое элемент принадлежит в массиве, а затем помещает его туда.

Псевдокод:

for i from 1 to N
 	key = a[i]
	 j = i - 1
 	while j >= 0 and a[j] > key
    		a[j+1] = a[j]
    		j = j - 1
 	a[j+1] = key

Сортировка по куче:

Сортировка кучи - это алгоритм, основанный на сравнении, который использует двоичную структуру данных кучи для сортировки элементов. Он разделяет входные данные на отсортированную и несортированную области и итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область.

Псевдокод:

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i,n)

Heapify(A as array, i as int, n as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else 
        max = i

    if (right<=n) and (A[right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)

Сортировка слиянием

Сортировка слиянием - это алгоритм, основанный на сравнении, который фокусируется на том, как объединить два предварительно отсортированных массива, чтобы полученный массив также был отсортирован.

Псевдокод:

func mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end func

func merge( var a as array, var b as array )
   var c as array

   while ( a and b have elements )
        if ( a[0] > b[0] )
             add b[0] to the end of c
             remove b[0] from b
        else
             add a[0] to the end of c
             remove a[0] from a
   while ( a has elements )
        add a[0] to the end of c
        remove a[0] from a
   while ( b has elements )
        add b[0] to the end of c
        remove b[0] from b
   return c
 end func

Быстрая сортировка:

Быстрая сортировка - это алгоритм, основанный на сравнении, который использует принцип «разделяй и властвуй» для сортировки массива. Алгоритм выбирает опорный элемент, A [q], а затем переупорядочивает массив на два подмассива A [p. . . . q-1], что все элементы меньше A [q] и A [q + 1. . . r], так что все элементы больше или равны A [q].

Псевдокод:

Quicksort(A as array, low as int, high as int){
    if (low < high){
        pivot_location = Partition(A,low,high)
        Quicksort(A,low, pivot_location)
        Quicksort(A, pivot_location + 1, high)
    }
}
Partition(A as array, low as int, high as int){
     pivot = A[low]
     leftwall = low

     for i = low + 1 to high{
         if (A[i] < pivot) then{
             swap(A[i], A[leftwall + 1])
             leftwall = leftwall + 1
         }
     }
     swap(pivot,A[leftwall])

    return (leftwall)}

Радиксная сортировка:

Radix Sort - это алгоритм несравнительной сортировки с асимптотической сложностью O (nd). Это один из самых эффективных и быстрых алгоритмов линейной сортировки. Радиксная сортировка была разработана для сортировки больших целых чисел. Поскольку целое число рассматривается как строка цифр, мы также можем называть его алгоритмом сортировки строк.

Псевдокод:

func Radixsort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        for i = 0 to n do
         count[key of(A[i]) in pass j]++
 
        for k = 1 to 10 do
         count[k] = count[k] + count[k-1]
 
        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--
 
        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]
 
    end for(j)
end func

Сравнение алгоритмов сортировки

Чтобы выбрать алгоритм сортировки для конкретной задачи, учитывайте время выполнения, сложность пространства и ожидаемый формат входного списка.

Здесь,

O = Big-O

Ω = Большой Омега

Θ = Тета

Big-O (O) - это показатель максимального времени, которое может потребоваться для выполнения алгоритма.
f (n) ≤ cg ( n), где f (n) и g (n) - неотрицательные функции, g (n) - верхняя граница, тогда f (n) - это Big O функции g (n).
Это обозначается как « f (n) = O (g (n)) ”

Big Omega (Ω) описывает лучшее, что может произойти для данного размера данных.
«f (n) ≥ cg (n)», это делает g (n) функция нижней границы.
Это обозначается как «f (n) = Ω (g (n))»

Theta (Θ) по сути означает, что функция f (n) ограничена сверху и снизу одной и той же функцией g (n).
f (n) является тэтой g (n) тогда и только тогда, когда f (n) = O (g (n)) и f (n) = Ω (g (n))
Это обозначается как « f (n) = Θ (g (n)) ”

Более подробную информацию можно найти в моем репозитории GitHub:

https://github.com/tssovi/implement-algorithms-in-c-and-python/tree/master/01-Sorting