Файл: Лекция 1. Сортировки.doc

Make it run,

Make it right,

Make it small,

Make it fast

Сделайте чтобы работало,

Сделайте чтобы работало правильно,

Сделайте чтобы было маленьким,

Сделайте чтобы работало быстро.

Лекция 1. Сортировки

Сортировки и поиск

В разделе описываются основные алгоритмы сортировки статических массивов.

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

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

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов необходимо выполнять in situ (на том же месте). Поэтому при выборе метода сортировки необходимо установить критерий эффективности, то есть определить ее быстродействие. При сортировке элементов в массиве выполняются два действия: сравнения элементов по некоторому ключу и пересылка элементов. И число сравнений (C), и число перестановок (M) зависят от размерности массива N.

Хорошие алгоритмы сортировки требуют порядка N*logN сравнений, более простые – порядка N² сравнений ключей. Хотя в более сложных алгоритмах меньше операций, сами эти операции более сложны; поэтому при достаточно малых N простые методы работают быстрее, но их не следует использовать при больших N.

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

• Исходная упорядоченность входного множества: во входном множестве могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе. Говорят, что сортировка демонстрирует естественное поведение, если C и M имеют наименьшие значения из возможных в случае упорядоченного массива и возрастают с ростом неупорядоченности, и неестественное поведение в противном случае.

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

Методы сортировки массива можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1. Сортировка выбором

2. Сортировка включениями

3. Сортировка обменом

Во всех программных примерах используются данные, определенные так:

• const N=… – целое положительное число, число элементов в массиве;

• type TData = array[1..N] of integer – сортируемые последовательности.

Результатом сортировки является массив, элементы которого упорядочены по возрастанию ключа. Для простоты ключом элемента считается значение самого элемента.

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

Это простой и наиболее очевидный способ сортировки. Его алгоритм состоит их двух шагов:

• Выбирается элемент с наименьшим ключом

• Меняется местами с первым элементом массива

После этого массив можно рассматривать как состоящий из двух частей: левой – уже отсортированной – «готовой», и правой, с которой будут повторяться те же шаги – «входной».

Понятно, что для сортировки всего массива нужно сделать N – 1 пар шагов: на N – 1 паре шагов два крайних правых элемента займут свои места, и массив станет упорядоченным.

Сортировка простым выбором показана в листинге 7.1. Процедура имеет только один параметр – сортируемый массив.

Листинг 7.1. Сортировка простым выбором. Вариант 1

procedure SortSelection(var a: TData);

var

i,j,imin : integer;

min :integer;

begin

for I:=1 to N – 1 do begin

min:=a[I]; imin:=i;

for j:=i+1 to N do // в этом цикле ищем минимальный элемент

if a[j]<min then

begin

min:=a[j]; imin:=j

end;

if i<>imin then

begin

a[imin]:=a[i]; // обмен местами мин. элемента с первым

a[i]:=min // из оставшейся – не отсортированной –

// части массива

end;

end;

end;

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

Для сравнения приводится этот же алгоритм, реализующий вышеприведенные отличия:

Листинг 7.2. Сортировка простым выбором. Вариант 2

procedure SortSelection1(var a: TData);

var

i,j,imin : integer;

tmp : integer;

begin

for i:=1 to N - 1 do begin

imin:=i;

for j:=i + 1 to N do // в этом цикле ищем минимальный элемент

if a[j]<a[imin] then imin:=j;

if i<>imin then begin

tmp:=a[imin]; // обмен местами мин. элемента с первым

a[imin]:=a[i]; // из оставшейся – не отсортированной

a[i]:=tmp //– части массива

end;

end;

end;

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

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

Число C сравнений ключей не зависит от исходной упорядоченности. C=1/2(N²-N). Число M перестановок минимально в случае изначальной упорядоченности: M~N и принимает наибольшее значение, если ключи изначально расположены в обратном порядке: M~trunc(N²/4)+3(N-1).

7.2. Сортировка включениями

7.2.1. Сортировка простыми включениями

Элементы массива условно разделяются на «готовую» последовательность a[1]…a[i] и «входную»: a[i+1]…a[N]. На каждом шаге, начиная с i=2, берут i-тый элемент массива – 1‑ый элемент «входной» последовательности и «вставляют» в нужное место «готовой» последовательности. Поскольку «вставить» между элементами массива новый элемент невозможно, приходится сдвигать j-тый элемент вправо, если вставляемый элемент меньше j-того, пока не найдется нужное место. Эта деятельность может закончиться при двух различных условиях:

• Найден элемент a[j], меньший, чем вставляемый элемент.

• Достигнут левый край массива.

Чтобы не использовать неэффективный цикл с двумя условиями, применим метод барьера, установив его в нулевой элемент массива. Для этого придется расширить диапазон индексов в описании массива до 0..N. Программа приведена в листинге 8.3.

Листинг 7.3. Сортировка простыми включениями

type

TData = array[0..N] of integer;

procedure SortInsertion(var a: TData); // Внимание! Массив должен

// начинаться с нуля!

var

i,j : integer;

tmp : integer;

begin

for i:=2 to N do begin

tmp:=a[i]; j:=i-1;

a[0]:=tmp; // установка барьера

while tmp<a[j] do begin

a[j+1]:=a[j]; // сдвинуть элемент

j:=j-1

end;

a[j+1]:=tmp // поставить элемент на свое место

end;

end; // SortInsertion

В сортировке простыми вставками число сравнений ключей при помещении i-того элемента на свое место составляет в среднем C_i ~i/2. Число пересылок M_i=C_i +2. Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший случай встречается, если элементы расположены в обратном порядке.

7.2.2. Сортировка бинарными включениями

Если воспользоваться отсортированностью «готовой» последовательности, то процесс вставки нового элемента может быть ускорен. Это достигается за счет применения бинарного (дихотомического) поиска места вставки очередного элемента. Программа приведена в листинге 8.4.

Листинг 7.4. Сортировка бинарными включениями

procedure SortBinInsert (var a: TData);

var

i,j,left,right,m: integer;

tmp : integer;

begin

for i:=2 to N do begin

tmp:=a[i]; left:=1; right:=i-1;

while left<=right do begin

m:=(left+right)div 2;//определение индекса среднего элемента

if tmp<a[m] then

right:=m-1 // сдвиг правой

else

left:=m+1 //или левой границы

end;

for j:=i-1 downto left do a[j+1]:=a[j]; // сдвиг элементов

a[left]:=tmp; // вставка элемента на нужное место

end;

end; // BinInsert

Число сравнений C~N*logN, так как поиск места вставки ищется каждый раз только в половине интервала. Но это улучшение касается только числа сравнений. Поскольку пересылка элементов – более трудоемкая операция, то это улучшение не является решающим: число перестановок по-прежнему ~N².

Для больших N сортировка вставками оказывается не очень подходящим методом: сдвиг ряда элементов для вставки одного – неэкономно. Казалось бы, гораздо эффективнее переставлять только некоторые элементы и на большие расстояния. Действительно, такой метод сортировки есть: это сортировка Шелла. Мы рассмотрим ее несколько позже.

7.3. Сортировка обменом

7.3.1 Сортировка простым обменом

Сортировка методом пузырька – это трогательное название запоминают все. Но далеко не все знают, что этот метод в полной мере воплощает принцип обменной сортировки: сравниваются и обмениваются местами два соседних элемента. При чем здесь пузырек? Если представить массив высоким и узким сосудом с жидкостью, а элементы массива – пузырьками, вес которых пропорционален величине ключа элемента, то каждый проход по массиву заставляет пузырек подняться кверху и занять место, соответствующее его весу. Алгоритм приведен в листинге 7.5.

Листинг 7.5. Сортировка методом пузырька

procedure SortBubble (var a: TData);

var

i,j: integer;

tmp : integer;

begin

for i:=2 to N do begin

for j:=N downto i do

if a[j-1]>a[j] then begin // сравнение элементов

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp // обмен местами

end

end;

end;

7.3.2. Шейкер-сортировка

Оптимизация предыдущего алгоритма включает в себя следующее:

• массив можно считать уже упорядоченным, если на последнем проходе не было ни одной перестановки элементов

• сравнение пар элементов можно производить только до места последней перестановки: раз не было перестановок, значит – дальше элементы упорядочены

• при прохождении массива слева направо (снизу вверх) поднимается легкий пузырек. Почему бы не двигаться по массиву в обратном направлении – сверху вниз, опуская тяжелый пузырек?

Эти моменты учтены в шейкер-сортировке (от англ. shake – трясти), приведенной в листинге 7.6.

Листинг 7.6. Шейкер-сортировка

procedure SortShaker (var a: TData);

var

j,left,right: integer;

tmp : integer;

last :integer; // место последней перестановки

begin

left:=2; right:=N; last:=N;

repeat

for j:=right downto left do //поднимаются легкие пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

left:=last+1; // запомнили место последней перестановки

for j:=left to right do //опускаются тяжелые пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

right:=last-1; // запомнили место последней перестановки

until left>right;

end; //Shaker

Число сравнений в алгоритме простого обмена равно C=1/2(N²-N), а минимальное и максимальное количества пересылок равны: M_min=0, M_max~(N²-N). Наименьшее число сравнений в шейкер-сортировке C_min=(N-1) – это соответствует единственному проходу по упорядоченному массиву.

Все усовершенствования сортировки обменом приводят только к уменьшению числа сравнений. Но поскольку именно перестановка элементов занимает, как правило, гораздо большее время, то эти усовершенствования не приводят к значительному эффекту. Анализ показывает, что сортировка методом пузырька (и даже ее улучшенный вариант – шейкер-сортировка) менее эффективна, чем сортировка вставками и обменом.

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

Рассмотрим одно из усовершенствований простой сортировки обменом – метод убывающих приращений. Оно заключается в том, что на каждом этапе сравниваются и обмениваются местами элементы, стоящие друг от друга на некотором расстоянии. Это расстояние (шаг) на первом этапе равно примерно половине длине массива, с каждым этапом уменьшается, и на последнем этапе шаг равен единице. Улучшение происходит оттого, что на начальных этапах в сортировке участвуют немного элементов, с каждым этапом повышается отсортированность массива, и на последнем этапе, который есть сортировка простыми вставками, массив уже почти отсортирован, и перемещений элементов немного.

В этой сортировке важен правильный выбор величины шагов. Анализ показывает, что величины шагов не должны быть кратны друг другу, чтобы достигнуть лучших результатов. Кнут рекомендует такие последовательности (записанные в обратном порядке):

1, 4, 13, 40, 121, … , где step_k-1=3*step_k+1,

1, 3, 7. 15, 31, …где step_k-1=2*step_k+1.

В листинге 7.7 шаги выбирались по формуле step_k= step_k-1*3/5, начиная с step₁=N div 2 и заканчивая шагом, равным единице.

Листинг 7.7. Сортировка Шелла

procedure SortShell (var a: TData);

var

i,j,k,step: integer;

tmp : integer;

begin

step:=N div 2; // первый шаг

while step>=1 do begin

k:=step;

for i:=k+1 to N do begin

tmp:=a[i]; j:=i-k;

while (j>0) and (tmp<a[j]) do begin

a[j+k]:=a[j]; j:=j-k

end;

a[j+k]:=tmp

end;

step:=3*step div 5; // определение следующего шага

end;

end; // Shell

Анализ сортировки Шелла показывает, что порядок ее алгоритма ~N. Это – значительное улучшение по сравнению с «родительской» сортировкой простыми вставками, порядок которой ~N².

7.5. Сортировка подсчетом

Рассмотренные сортировки производились in situ – на том же месте. При наличии достаточного количества памяти можно переписывать элементы из одного массива в другой сразу в нужном порядке. Тогда число наиболее трудоемких операций – пересылок элементов – будет точно N. Разумеется, для определения номера элемента в новом массиве придется сделать какое-то количество сравнений.

В качестве примера возьмем очень простую сортировку методом подсчета. Ее идея заключается в том очевидном факте, что i-й ключ в упорядоченном массиве превышает ровно i-1 остальных ключей, если никакие два ключа не равны. Таким образом, идея состоит в том, чтобы сравнить попарно все ключи и подсчитать, сколько из них меньше каждого отдельного ключа. Сравнить попарно – означает, что достаточно один раз сравнить a[i] и a[j], причем j # i. Для подсчетов числа ключей, меньших данного, используется вспомогательный массив cnt[1..N] of integer, окончательные значения которого служат для пересылки элементов из исходного массива в новый. Для минимального элемента исходного массива значение соответствующего элемента массива счетчиков равно нулю, а стоять минимальный элемент должен на первом месте. Поэтому массив счетчиков инициализируется единицами.