Сортировка

Сортировка — это процесс размещения элементов в списке в некоторой числовой или лексикографической последовательности (порядке). Различаются следующие виды сортировки.

Обменная сортировка. При этом способе наименьший элемент выдвигается в начало списка, следующий по величине — на вторую позицию и т.д. Для списка N элементов производится N(N – 1)/2, т.е. O(N²) операций. Естественно, что для больших значений N использование этой сортировки нецелесообразно.

Алгоритм:

EXCHANGE_SORT procedure(LIST,N);

declare LIST(N); /* массив сортировки */

do I=1 to N-1;

do J=I+1 to N;

if LIST(J)< LIST(I) then

Reverse(LIST(J), LIST(I));

end;

end;

end EXCHANGE_SORT;

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

Алгоритм:

MERGE_SORT procedure(LIST,N);

declare LIST(N); /* массив сортировки */

call MERGE_SORT(LIST(1:N/2),N/2,

(LIST(N/2+1:N),N/2));

/* объединение отсортированных списков */

end MERGE_SORT;

Процедура слияния отсортированных списков размером K выполняется за 2×K операций путем просмотра первого элемента в каждом списке и перенесения меньшего из двух в новый список. Эти два действия повторяются для каждого из 2×K элементов списка, получается 4×K операций. Так как каждый из списков уже отсортирован, нужно проверить только первые элементы. Хотя для реализации этого способа нужна память большого объема, время сортировки путем последовательного разбиения каждого из подсписков на два можно уменьшить до величины