Вот список из 5 типичных алгоритмов сортировки с исчерпывающими пояснениями и псевдокодом для легкого переноса на любой язык.

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

Многократно меняет местами соседние элементы, сравнивая их, пока массив не будет отсортирован. Не подходит для больших массивов. Шаги следующие:

  1. Инициализировать переменную для отслеживания свопов swaps = 0
  2. пройтись по массиву do <perform_swaps> while swaps > 0 до тех пор, пока swaps›0 (т.е. массив не отсортирован)
  3. In perform_swaps :
  • for i = 0 to n — 1 (цикл от первого ко второму и последнему элементу. Это потому, что последний элемент не будет иметь соседа справа от него для сравнения)
  • Для каждого элемента: if arr[i] > arr[i+1]сравните, являются ли этот элемент и его сосед неупорядоченными
  • Если они есть, поменяйте их местами: tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp . Не забудьте обновить счетчик свопов: swaps++

Вот и все! Алгоритм, хотя и простой, очень неэффективен, поскольку использует временную сложность O (N²) в наихудшем случае.

Сортировка выбором

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

  1. Перебрать все элементы, кроме последнего (поскольку этот не сможет двигаться): for i = 0 to n — 1
  • Найдите наименьший элемент индекса:
  • – min_i = i начальный наименьший элемент установлен в текущий элемент
  • - for j = i + 1 to n цикл по всем последующим элементам
  • – if arr[j] < arr[min_i]: min_i = j установить минимальный индекс в j, если элемент в j наименьший, чем предыдущий наименьший элемент
  • if min_i != i, если наименьший элемент не находится в правильной позиции (это будет i, так как все до i уже отсортировано)
  • – tmp = arr[min_i]; arr[min_i] = arr[i]; arr[i] = tmp затем поменяйте местами элементы, поместив таким образом элемент в min_i в правильную позицию

Алгоритм очень прост, но также очень неэффективен, как пузырьковая сортировка, и имеет временную сложность O(N²).

Сортировка вставками

Алгоритм сортировки вставками будет перебирать все элементы массива (кроме первого), сравнивая каждый элемент с его предшественником. Если они не в правильном порядке, мы меняем ключ (текущий элемент) и его предшественник и повторяем с новым предшественником, пока он не окажется в правильном месте.

  1. Цикл по всем элементам в массиве, кроме первого (поскольку у него нет предшественника): for i = 1 to n
  • key = arr[i]; predi = i — 1 инициализировать переменные для текущего значения и предшествующего индекса
  • while predi >= 0 and arr[predi] > keyпроходим по всем предшественникам, пока не встретим начало массива или ключ не будет правильно расположен
  • – arr[predi + 1] = arr[predi] переместить предшественника вверх
  • – predi-- вернуться к предшественнику
  • arr[predi + 1] = key как только мы нашли истинного предшественника ключа, мы вставляем его на одну позицию выше него.

Подобно сортировке выбором и пузырьковой сортировкой, сортировка вставками занимает O (N²) временную сложность.

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

Сортировка слиянием — это алгоритм «разделяй и властвуй». Он разделит список на два, отсортирует их с помощью сортировки слиянием и рекомбинирует их так, чтобы они были отсортированы, что-то вроде двоичного поиска в форме сортировки. Следующий блок кода, поскольку сложно последовательно представить рекурсивный алгоритм в виде списка (обратите внимание, что он был написан в несколько стиле C с использованием указателей и переходов):

// takes in pointer to first element and length of arr
// and returns pointer to sorted list
int *merge_sort(int *arr, int length)
    // array is sorted if length = 1
    if length == 1: return arr
    
    // length of new arrays is half of this one
    int left_len = length/2
// left side:
    int *l = merge_sort(arr,left_len)
// right side adds length%2 as if length is not
// divisible by two, we add one to the length
// and sort an extra element in the right side
    rlen = left_len + length%2
// we then merge_sort starting at element right after
// last element in left side
   int *r = merge_sort(arr+left_len,rlen)
    // merging:
    int i = 0 // index for left side
    int j = 0 // index for right side
    int n = 0 // index where we insert element at new array
    int n_arr[length] // declare array of size length
    while true:
        // break when we have gone through all
        // elements in both arrays
        if i >= left_len and j >= rlen: break
// if no elements in left side, j wins
        elif i >= left_len: goto j_wins
// if no elements in right side, i wins
        elif j >= rlen: goto i_wins
        if arr[i] > arr[j]:
           i_wins:
               n_arr[n] = arr[i]
               // progress n and i
               n++; i++
        else:
           j_wins:
               n_arr[n] = arr[j]
               n++; j++
     return n_arr

Это создает алгоритм O (NlogN), лучше, чем N²

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

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

void quicksort(arr[], start_i, end_i)
    if (start_i >= end_i) return; // return for length 1/invalid arr
    // part will return the index of pivot, which should be in    correct place
    part_ix = part(arr,start_i,end_i)
    // we then recursively call quicksort to sort everything above and below our pivot:
    quicksort(arr,start_i,part_ix+1)
    quicksort(arr,part_ix-1,end_i)
int part(arr[], start_i, end_i)
    // there are many ways to define the pivot, however in this case we have chosen to make it the last element
    pivot = arr[end_i]
    // index of current 'correct' position of pivot will be the first element
    corri = start_i
    // loop through all possible positions of pivot within partition:
    for i = start_i to end_i
       // if element less than pivot, the pivot
       // is to the right of it, so we move that element
       // down and update our correct index to it
       if arr[i] < pivot
              // arr[corri] should be element to the right of pivot
              swap arr[i] arr[corri]
              corri++
    // finally, swap the last element into the
    // correct index and arr[corri] to end_i which
    // as we know it is to the right of end_i
    swap arr[end_i] arr[corri]
    return corri

Конец