6.4. Улучшенные методы сортировки

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

6.4.1. Быстрая сортировка (Quick Sort)

Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному. 





Слева от 6 располагают все ключи с меньшими, а справа - с большими или равными 6 (рис. 6.4).

Sub Sort (L, R) i = L j = R x = a((L + R) div 2) repeat while a(i) < x do i = i + 1 endwhile while a(j) > x do j = j - 1 endwhile if i <= j then y = a(i) a(i) = a(j) a(j) = y i = i + 1 j = j - 1 endif until i > j if L < j then sort (L, j) endif if i < R then sort (i, R) endif return sub QuickSort sort (1, n) return

procedure Sort (L, R: integer); begin i := L; j := r; x := a[(L + r) div 2]; repeat while a[i] < x do i := i + 1;  while a[j] > x do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1 end; until i > j; if L < j then sort (L, j); if i < r then sort (i, r); end; procedure QuickSort; begin sort (1, n); end;

Эффективность алгоритма:

О(n log n) - самый эффективный метод.

6.4.2 Сортировка Шелла (сортировка с уменьшающимся шагом)

В 1959 году Д. Об этом говорит сайт https://intellect.icu . Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Работа его представлена на рис. 6.5:




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

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

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

Приводимый алгоритм основан на методе прямой вставки без барьера и не ориентирована на некую определенную последовательность расстояний, хотя в нем для конкретности заданы шаги 5, 3 и 1.

При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, и программу для определения его местонахождения необходимо делать насколько возможно простой. Поэтому приходится расширять массив до [-h1..N].


h[1..t] - массив размеров шагов

a[1..n] - сортируемый массив

k - шаг сортировки

x - значение вставляемого элемента

Subroutine ShellSort Псевдокод: const t = 3 h(1) = 5 h(2) = 3 h(3) = 1 for m = 1 to t k = h(m) for i = k + 1 to n x = a(i) for j = i - k to 1 step -k if x < a(j) then  a( j+k) = a(j) else  goto L endif next j L: a(j+k) = x next i next m return

Паскаль: const t = 3; h(1) = 5; h(2) = 3; h(3) = 1; var h: array [1..t] of integer; a: array [1..n] of integer; k, x, m, t, i, j: integer; begin for m = 1 to t do begin k:= h(m); for i = k + 1 to n do begin x:= a(i);  for j = i-k downto k do begin if x < a(j ) then a(j+k):= a(j); else  goto 1; end ; end; end; 1: a(j+1) = x ; end;  end .

Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. 
Д. Кнут предлагает такую последовательность шагов (в обратном порядке): 1, 3, 7, 15, 31, … То есть: h _m-1 = h _m + 1, 
t = log₂n - 1. При такой организации алгоритма его эффективность имеет порядок O ( n^1.2)


Контрольные вопросы

1. 
   Что такое сортировка?
2. 
   Назовите основные методы сортировки.
3. 
   Какие методы сортировки относятся к строгим?
4. 
   Какие методы сортировки относятся к улучшенным?
5. 
   Какая сортировка называется устойчивой?
6. 
   В чем состоит суть метода прямого включения?
7. 
   В чем состоит суть метода прямого выбора?
8. 
   В чем состоит суть метода прямого обмена?
9. 
   Назовите разницу между этими тремя методами.
10. 
    Какой метод сортировки является самым эффективным?
11. 
    К какому из основных методов относится метод Шелла?

На этом все! Теперь вы знаете все про улучшенные методы сортировки, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое улучшенные методы сортировки и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных

Из статьи мы узнали кратко, но содержательно про улучшенные методы сортировки

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.