Алгоритмы сортировки

Введение

Часто нужно упорядочить предметы по какому-то признаку: записать данные числа в порядке возрастания, слова — по алфавиту, людей выстроить по росту. Если можно сравнить любые два предмета из данного набора, то этот набор всегда можно упорядочить. Процесс упорядочивания информации и называют «сортировкой»^[1].

Пусть нам требуется упорядочить набор $\{3,6,1,2,9,5\}$ по возрастанию. Это лёгкая задача, ответ будет таким: $\{1,2,3,5,6,9\}$ .

Для информатиков намного занимательнее вопрос, как был получен ответ. Человек, скорее всего, будет работать так. Перед глазами у него записан беспорядочный набор чисел. Если числа большие и их много, ему обязательно потребуется дополнительное запоминающее устройство, например карандаш с бумагой.

Исходный набор:  3, 6, 1, 2, 9, 5 (где-то написано)
Вывод: (чистый лист бумаги)

Находим наименьшее число (в нашем примере — 1), записываем на свой лист бумаги и вычёркиваем из данного набора.

Исходный набор:  3, 6, 1, 2, 9, 5
Вывод: 1

Теперь из оставшихся в исходном наборе чисел снова выберем самое маленькое — на этот раз им будет 2. Удалим её из исходного набора и допишем в результат сортировки:

Исходный набор:  3, 6, 1, 2, 9, 5
Вывод: 1, 2

Потом «переносим» тройку и так далее.

 3, 6, 1, 2, 9, 5
1, 2, 3

3, 6, 1, 2, 9, 5
1, 2, 3, 5

3, 6, 1, 2, 9, 5
1, 2, 3, 5, 6

Исходный набор: 3, 6, 1, 2, 9, 5
Вывод: 1, 2, 3, 5, 6, 9.

Исходный набор пуст, все числа записаны на «новом листе бумаги» в нужном порядке: по возрастанию.

Сортировка поиском минимума

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

Реализация алгоритма

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

После k-го хода результат содержит k чисел, а исходный набор — N-k. Договоримся, что текущий результат мы будем хранить в первых k элементах массива. Разберем подробнее, как это можно реализовать. Для этого вновь обратимся к нашему примеру:

3, 6, 1, 2, 9, 5.

На первом шаге мы находим наименьшее число — 1 — и должны переместить его на первое место. Но там уже записано число 3, куда же его деть? Ответ прост: на место числа 1. Таким образом, мы просто меняем местами два элемента массива:

1 | 6, 3, 2, 9, 5.

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

На втором шаге мы находим минимальное число в правой части — среди элементов массива со 2-го по 6-й (в общем случае — по N-й) — и меняем его местами с числом, стоящим на втором месте:

1, 2 | 3, 6, 9, 5.

Далее нам следует поставить следующее минимальное число — 3 — на третье место, но оно уже и так там стоит. Впрочем, мы не будем обращать на это внимание, и просто как бы поменяем его само с собой:

1, 2, 3 | 6, 9, 5.

Попробуем записать действия, которые нам предстоит проделать на шаге с номером k. Сначала нам нужно найти наименьшее среди чисел, записанных в k, k+1, ..., N позициях массива. После этого нам нужно поменять этот элемент с k-м.

Сколько таких шагов нужно сделать, чтобы полностью отсортировать массив? Напрашивается ответ "N", но не будем торопиться. Пусть сделан N-1 шаг. Тогда в правой, неотсортированной части массива останется одно число. Какое это число? Ясно, что это самое большое число в массиве. Где оно в итоге должно оказаться? На последнем месте в массиве. Но оно уже и так там! Поэтому N-й шаг алгоритма выполнять не нужно.

Таким образом, алгоритм можно записать следующим образом (на некотором условном языке, который мы нигде не будем описывать, но всюду будем использовать: надеемся, он будет интуитивно понятен всем читателям):

for k:=1 to N-1 do begin
  Выполнить k-й шаг алгоритма 
end

В чем заключается k-й шаг, мы уже тоже выяснили, поэтому можно расписать алгоритм подробнее:

for k:=1 to N-1 do begin
  Найти наименьший среди элементов массива с номерами k..N
  Поменять его местами с k-м элементом
end

Будем считать, что массив называется a, и напишем соответствующий код, вспомнив, как искать минимальный элемент и как менять два элемента местами:

for k:=1 to N-1 do begin
  min:=k;
  for i:=k+1 to N do
    if a[i]<a[min] then min:=i;
  temp:=a[min]; a[min]:=a[k]; a[k]:=temp;
end

Алгоритм сортировки поиском минимума реализован.

Анализ работы алгоритма

Предположим, что кто-то придумал еще один алгоритм сортировки. Как сравнить его с нашим? Чем он может быть лучше или хуже? Ясно, что результаты работы обоих алгоритмов обязаны совпадать, в противном случае можно сказать, что один из них работает неправильно. Таким образом, алгоритмы надо сравнивать по другим параметрам. Этими параметрами, в первую очередь, являются время работы алгоритма и требуемая для его работы память. Поскольку сравнивать наш алгоритм пока не с чем, попробуем просто оценить его по названным параметрам.

Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а количество операций, выполняемых алгоритмом. Наш алгоритм N-1 раз выполняет поиск минимума - в первый раз минимум ищется среди N элементов, и на это требуется порядка N операций, второй раз - среди N-1 элемента, и т. д. Таким образом, на поиск минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 операций, что примерно равно N²/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N²/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N²/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN²/2 операций (где С - некоторая константа, не зависящая от N), называют квадратичными. Посмотрим, как растет величина N² с ростом N:

N    10     1,000      10,000         1,000,000
N²  100 1,000,000 100,000,000 1,000,000,000,000

Видно, что уже при N равном миллиону количество операций достигает триллиона!

Теперь посмотрим, как используется память. Мы не используем никакой дополнительной памяти, кроме той, в которую записан исходный массив. Казалось бы, меньше памяти использовать нельзя! Это не совсем точное утверждение.

Термин «сортировка»

^ «Сортировка» в её данном значении — это варваризм, пришедший к нам из английского компьютерного жаргона. Ни русское слово «сортировать» (пришедшее, скорее всего, из немецкого), ни английское to sort в его общеупотребительном значении, ни исходное латинское существительное sors никак не относятся к смыслу «упорядочивать по величине».

См. также

В Википедии: