Модели и структуры данных



         

Сортировки выборкой - часть 4


Если по окончании прохода значение этой переменной останется 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

Таблица 3.6

Еще одна модификация пузырьковой сортировки носит название шейкер-сортировки.


Содержание  Назад  Вперед