Сортировки выборкой

СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи-

чески "дословно" сформулированную выше стратегию выборки. Порядок

алгоритма простой выборки - 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. Двоеточием показана граница между входным и выход-

ным множествами.

Таблица 3.5

┌────────┬──────────────────────────────────────────┐

│ шаг │ содержимое массива a │

├────────┼──────────────────────────────────────────┤

│исходный│: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.

 

 

Таблица 3.6

┌─────────┬────┬──────────────────────────────────────────┐

│ шаг │ nn │ содержимое массива a │

├─────────┼────┼──────────────────────────────────────────┤

│исходный │ 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 │

└─────────┴────┴──────────────────────────────────────────┘