Сортировка вставкой

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

Алгоритм для сортировки массива из N элементов.

1. Начинаем сортировку со 2-го элемента: i:=2.

2. Запоминаем в отдельную переменную temp значение i-го элемента.

3. Начинаем поиск места нового элемента с позиции j=i-1.

4. Если j>0 и j-ый элемент больше temp, то помещаем j-ый элемент на позицию j+1, уменьшаем значение j на 1 и возвращаемся к шагу 4.

5. Помещаем значение temp на позицию j+1.

6. Если i < N, то увеличиваем значение i на 1 и возвращаемся к шагу 2.

7. Конец алгоритма. Массив отсортирован.

Пример: алгоритм сортировки вставкой массива str

for i := 2 to n do

begin

temp := str[ i ];

j := i-1;

while (j>=1) and (str[ j ]>temp) do

begin

str[j+1] := str[j];

dec(j);

end;

str[j+1] := temp;

end;

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

Еще одна простая сортировка, которая будет рассмотрена в данном параграфе, – это пузырьковая сортировка, которая относится к категории обменных. Здесь периодически просматривается массив и обмениваются, если нужно, близлежащие элементы – до тех пор, пока никаких обменов не потребуется.

Алгоритм для сортировки массива из N элементов.

1. Начинаем сортировку до N-го элемента: i:=N.

2. Начинаем просматривать элементы со 2-го: j:=2.

3. Если элемент j-1 больше элемента j, то меняем их местами.

4. Увеличиваем значение j на 1 (inc(j)).

5. Если j < i, то переходим к шагу 3.

6. Уменьшаем значение i на 1 (dec(i))

7. Если i > 1, то возвращаемся к шагу 2.

8. Конец алгоритма. Массив отсортирован.

Пример: алгоритм пузырьковой сортировки массива str

for i := n downto 2 do

for j:=2 to i do

if str[ j-1 ] > str[ j ] then

begin

t := str[ j-1 ];

str[ j-1 ] := str[ j ];

str[ j ] := t;

end;

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность ~N², к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным лишь при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.

Среди улучшенных сортировок можно выделить сортировки Шелла, пирамидальную и др.

Существует так называемая «Быстрая сортировка», имеющая среднюю сложность порядка N*logN, являющаяся усовершенствованием обменных сортировок. Реализация такой сортировки наиболее удобна в рекурсивном варианте.

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

Вопросы для самопроверки

1. В чем суть алгоритма бинарной сортировки данных?

2. В чем суть алгоритма пузырьковой сортировки данных?

3. В чем суть алгоритма сортировки данных вставкой?

4. Какие улучшенные алгоритмы сортировки данных Вы знаете?