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

Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного та- кого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по вевеличине ключа элемент и т.д. Для постановки на свои места 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	Содержимое массива а
Исходный		717 473 313 160 949 764_34 467 757 800:
		473 313 160 717 764_34 467 757 800:949
		313 160 473 717_34 467 757:764 800 949
		160 313 473_34 467:717 757 764 800 949
		160 313_34 467:473 717 757 764 800 949
		160_34:313 467 473 717 757 764 800 949
		_34:160 313 467 473 717 757 764 800 949
Результат		: 34 160 313 467 473 717 757 764 800 949

Таблица 3.6

Еще одна модификация пузырьковой сортировки носит название шейкер-сортировки. Суть ее состоит в том, что направления просмотров чередуются: за просмотром от начала к концу следует просмотр от конца к началу входного множества. При просмотре в прямом направлении запись с самым большим ключом ставится на свое место в последовательности, при просмотре в обратном направлении - запись с самым маленьким. Этот алгоритм весьма эффективен для задач восстановления упорядоченности, когда исходная последовательность уже была упорядочена, но подверглась не очень значительным изменениям. Упорядоченность в последовательности с одиночным изменением будет гарантированно восстановлена всего за два прохода.

Сортировка Шелла.

Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии 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
		32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
		32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
		_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
		_1_ 4 17_ 4 18 13 20 22 32 40 49 76 52 77 57 96
		_1_ 4_ 4 17 13 18 20 22 32 40 49 52 76 57 77 96
		_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
Результат		_1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96

Таблица 3.7

Сортировки включением

Сортировка простыми вставками.

Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N^2/4 перемещений, что де- лает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.

Алгоритм сортировки простыми вставками иллюстрируется программным примером 3.11.

{===== Программный пример 3.11 =====} Procedure Sort(a: Seq; var b: Seq); Var i, j, k: integer; begin for i:=1 to N do begin { перебор входного массива } { поиск места для a[i] в выходном массиве } j:=1; while (j < i) and (b[j] <= a[i]) do j:=j+1; { освобождение места для нового эл-та } for k:=i downto j+1 do b[k]:=b[k-1]; b[j]:=a[i]; { запись в выходной массив } end; end;

Эффективность алгоритма может быть несколько улучшена при применении не линейного, а дихотомического поиска. Однако, следует иметь в виду, что такое увеличение эффективности может быть достигнуто лишь на множествах значительного по количеству элементов объема. Т.к. алгоритм требует большого числа пересылок, при значительном объеме одной записи эффективность может определяться не количеством операций сравнения, а количеством пересылок.

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

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: