Сортировки выборкой
Сортировка простой выборкой.
Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N^2). Количество пересылок - N.
Алгоритм сортировки простой выборкой иллюстрируется программным примером 3.7.
В программной реализации алгоритма возникает проблема значения ключа "пусто". Довольно часто программисты используют в качестве такового некоторое заведомо отсутствующее во входной последовательности значение ключа, например, максимальное из теоретически возможных значений. Другой, более строгий подход - создание отдельного вектора, каждый элемент которого имеет логический тип и отражает состояние соответствующего элемента входного множества ("истина" - "непусто", "ложь" - "пусто"). Именно такой подход реализован в нашем программном примере. Роль входной последовательности здесь выполняет параметр a, роль выходной - параметр b, роль вектора состояний - массив c. Алгоритм несколько усложняется за счет того, что для установки начального значения при поиске минимума приходится отбрасывать уже "пустые" элементы.
{===== Программный пример 3.7 =====} Procedure Sort( a : SEQ; var b : SEQ); Var i, j, m : integer; c: array[1..N] of boolean; {состояние эл-тов вх.множества} begin for i:=1 to N do c[i]:=true; { сброс отметок} for i:=1 to N do {поиск 1-го невыбранного эл. во вх.множестве} begin j:=1; while not c[j] do j:=j+1; m:=j; { поиск минимального элемент а} for j:=2 to N do if c[j] and (a[j] < a[m]) then m:=j; b[i]:=a[m]; { запись в выходное множество} c[m]:=false; { во входное множество - "пусто" } end; end;
Обменная сортировка простой выборкой.
Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется его, так называемый, обменный вариант. При обменной сортировке выборкой входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части.
В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.
Обменная сортировка простой выборкой показана в программном примере 3.8. Процедура имеет только один параметр - сортируемый массив.
{===== Программный пример 3.8 =====} Procedure Sort(var a : SEQ); Var x, i, j, m : integer; begin for i:=1 to N-1 do { перебор элементов выходного множества} { входное множество - [i:N]; выходное - [1:i-1] } begin m:=i; for j:=i+1 to N do { поиск минимума во входном множестве } if (a[j] < a[m]) then m:=j; { обмен 1-го элемента вх. множества с минимальным } if i<>m then begin x:=a[i]; a[i]:=a[m]; a[m]:=x; end;end; end;
Результаты трассировки программного примера 3.8 представлены в таблице 3.5. Двоеточием показана граница между входным и выходным множествами.
| Шаг | Содержимое массива а |
| Исходный | :242 447 286 708_24_11 192 860 937 561 |
| 1 | _11:447 286 708_ 24 242 192 860 937 561 |
| 2 | _11_24:286 708 447 242 192 860 937 561 |
| 3 | _11_24 192:708 447 242 286 860 937 561 |
| 4 | _11_24 192 242:447 708 286 860 937 561 |
| 5 | _11_24 192 242 286:708 447 860 937 561 |
| 6 | _11_24 192 242 286 447:708 860 937 561 |
| 7 | _11_24 192 242 286 447 561:860 937 708 |
| 8 | _11_24 192 242 286 447 561 708:937 860 |
| 9 | _11_24 192 242 286 447 561 708 860:937 |
| Результат | _11_24 192 242 286 447 561 708 860 937: |
Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но порядок алгоритма остается степенным - O(n^2). Количество перестановок N-1, но перестановка, по-видимому, вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.
Довольно простая модификация обменной сортировки выборкой предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума и обмен их с первым и с последним элементами множества соответственно.
Хотя итоговое количество сравнений и пересылок в этой модификации не уменьшается, достигается экономия на количестве итераций внешнего цикла.
Приведенные выше алгоритмы сортировки выборкой практически нечувствительны к исходной упорядоченности. В любом случае поиск минимума требует полного просмотра входного множества. В обменном варианте исходная упорядоченность может дать некоторую экономию на перестановках для случаев, когда минимальный элемент найден на первом месте во входном множестве.
Пузырьковая сортировка.
Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного та- кого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходное множество, таким образом, формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.
Порядок пузырьковой сортировки - O(N^2). Среднее число сравнений - N*(N-1)/2 и таково же среднее число перестановок, что значительно хуже, чем для обменной сортировки простым выбором. Однако, то обстоятельство, что здесь всегда сравниваются и перемещаются только соседние элементы, делает пузырьковую сортировку удобной для обработки связных списков. Перестановка в связных списках также получается более экономной.
Еще одно достоинство пузырьковой сортировки заключается в том, что при незначительных модификациях ее можно сделать чувствительной к исходной упорядоченности входного множества. Рассмотрим некоторые их таких модификаций.
Во-первых, можно ввести некоторую логическую переменную, которая будет сбрасываться в false перед началом каждого прохода и устанавливаться в true при любой перестановке.
Если по окончании прохода значение этой переменной останется false, это означает, что менять местами больше нечего, сортировка закончена. При такой модификации поступление на вход алгоритма уже упорядоченного множества потребует только одного просмотра.
Во-вторых, может быть учтено то обстоятельство, что за один просмотр входного множества на свое место могут "всплыть" не один, а два и более элементов. Это легко учесть, запоминая в каждом просмотре позицию последней перестановки и установки этой позиции в качестве границы между множествами для следующего просмотра. Именно эта модификация реализована в программной иллюстрации пузырьковой сортировке в примере 3.9. Переменная nn в каждом проходе устанавливает верхнюю границу входного множества. В переменной x запоминается позиция перестановок и в конце просмотра последнее запомненное значение вносится в nn. Сортировка будет закончена, когда верхняя граница входного множества станет равной 1.
{===== Программный пример 3.9 =====} Procedure Sort( var a : seq); Var nn, i, x : integer; begin nn:=N; { граница входного множества } repeat x:=1; { признак перестановок } for i:=2 to nn do { перебор входного множества } if a[i-1] > a[i] then begin { сравнение соседних эл-в } x:=a[i-1]; a[i-1]:=a[i]; a[i]:=x; { перестановка } x:=i-1; { запоминание позиции } end; nn:=x; { сдвиг границы } until (nn=1); {цикл пока вых. множество не захватит весь мас.} end;
Результаты трассировки программного примера 3.9 представлены в таблице 3.6.
| Шаг | nn | Содержимое массива а |
| Исходный | 10 | 717 473 313 160 949 764_34 467 757 800: |
| 1 | 9 | 473 313 160 717 764_34 467 757 800:949 |
| 2 | 7 | 313 160 473 717_34 467 757:764 800 949 |
| 3 | 5 | 160 313 473_34 467:717 757 764 800 949 |
| 4 | 4 | 160 313_34 467:473 717 757 764 800 949 |
| 5 | 2 | 160_34:313 467 473 717 757 764 800 949 |
| 6 | 1 | _34:160 313 467 473 717 757 764 800 949 |
| Результат | : 34 160 313 467 473 717 757 764 800 949 |
Еще одна модификация пузырьковой сортировки носит название шейкер-сортировки.
Суть ее состоит в том, что направления просмотров чередуются: за просмотром от начала к концу следует просмотр от конца к началу входного множества. При просмотре в прямом направлении запись с самым большим ключом ставится на свое место в последовательности, при просмотре в обратном направлении - запись с самым маленьким. Этот алгоритм весьма эффективен для задач восстановления упорядоченности, когда исходная последовательность уже была упорядочена, но подверглась не очень значительным изменениям. Упорядоченность в последовательности с одиночным изменением будет гарантированно восстановлена всего за два прохода.
Сортировка Шелла.
Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при d=1. Качественный порядок сортировки Шелла остается O(N^2), среднее же число сравнений, определенное эмпирическим путем - log2(N)^2*N. Ускорение достигается за счет того, что выяв- ленные "не на месте" элементы при d>1, быстрее "всплывают" на свои места.
Пример 3.10 иллюстрирует сортировку Шелла.
{===== Программный пример 3.10 =====} Procedure Sort( var a : seq); Var d, i, t : integer; k : boolean; { признак перестановки } begin d:=N div 2; { начальное значение интервала } while d > 0 do { цикл с уменьшением интервала до 1 } begin k:=true; {пузырьковая сортировка с интервалом d} while k do { цикл, пока есть перестановки } begin k:=false; i:=1; for i:=1 to N-d do { сравнение эл-тов на интервале d } begin if a[i] > a[i+d] then begin t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; { перестановка } k:=true; { признак перестановки } end; { if ... } end; { for ... } end; { while k } d:=d div 2; { уменьшение интервала } end; { while d>0 } end;
Результаты трассировки программного примера 3.10 представлены в таблице 3.7.
| Шаг | d | Содержимое массива а |
| Исходный | 76 22_ 4 17 13 49_ 4 18 32 40 96 57 77 20_ 1 52 | |
| 1 | 8 | 32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52 |
| 2 | 8 | 32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52 |
| 3 | 4 | 13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57 |
| 4 | 4 | 13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57 |
| 5 | 2 | 13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57 |
| 6 | 2 | 13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57 |
| 7 | 2 | _1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57 |
| 8 | 2 | _1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57 |
| 9 | 1 | _1_ 4 17_ 4 18 13 20 22 32 40 49 76 52 77 57 96 |
| 10 | 1 | _1_ 4_ 4 17 13 18 20 22 32 40 49 52 76 57 77 96 |
| 11 | 1 | _1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96 |
| 12 | 1 | _1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96 |
| Результат | _1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96 |
