Что такое алгоритм сортировки?
Алгоритм сортировки - это алгоритм, который размещает элементы списка в определенном порядке. Наиболее часто используемые порядки - это числовой и лексикографический порядок.
Эффективная сортировка важна для оптимизации эффективности других алгоритмов, которые требуют, чтобы входные данные были в отсортированных списках.
Список наиболее часто используемых алгоритмов сортировки
Основные алгоритмы сортировки:
- Пузырьковая сортировка
- Выбор Сортировка
- Вставка сортировки
- Сортировка кучи
- Сортировка слиянием
- Быстрая сортировка
Алгоритмы предварительной сортировки:
- Радиксная сортировка
Пузырьковая сортировка:
Пузырьковая сортировка - это алгоритм, основанный на сравнении, который сравнивает каждую пару элементов в массиве и меняет их местами, если они не в порядке, пока не будет отсортирован весь массив. Для каждого элемента в списке алгоритм сравнивает каждую пару элементов.
Псевдокод:
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