§ 64. Сортировка

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

Возникает естественный вопрос: зачем сортировать данные? На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации.

Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быстрые. Мы изучим два классических метода из первой группы и один метод из второй — знаменитую «быструю сортировку», предложенную Ч. Хоаром.

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

Метод пузырька (сортировка обменами)

Название этого метода произошло от известного физического явления — пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» элемент (элемент с минимальными значениями), затем следующий и т. д.

Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т. д. (рис. 8.11).

После обработки пары (А[1], А[2]) минимальный элемент стоит на месте А[1]. Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так:

 

нц для j от N-1 до 1 шаг -1

      если A[j+l]<A[j] то

              поменять местами A[j] и A[j+1]

     все

кц

 

Здесь j — целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы A[j] и A[j+1], поэтому цикл начинается с j = N - 1. Если начать с = N, то на первом же шаге получаем выход за границы массива — обращение к элемен¬ту A[N+l].

За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй элемент, нужно написать ещё один почти такой же цикл, который будет отличаться только конечным значением / в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать:

 

нц для j от N-1 до | 2 | шаг -1

         если A[j+l]<A[j] то

              поменять местами A[j] и A[j+1]

         все

кц

При установке 3-го элемента конечное значение для / будет 3 и т. д. Таких циклов нужно сделать N - 1: на 1 меньше, чем количество элементов массива. Почему не N1 Дело в том, что если N — 1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место — другого места нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл:

 

нц для i от 1 до N-1

      нц для  j   от  N-1  до  i   шаг  -1

             если А[j +11<А[j]   то

                      поменять  местами A[j]   и  A[j+1]

             все

    кц

кц

           

Записать полную программу на выбранном языке вы можете самостоятельно.

 

Метод выбора

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

 

нц для i от 1 до N-1

        найти номер nMin минимального элемента из A[i]..A[N] 

 

Здесь перестановка происходит только тогда, когда найденный минимальный элемент стоит не на своём месте, т. е. I<>nMin. Поскольку поиск минимального элемента выполняется в цикле, этот алгоритм сортировки также представляет собой вложенный цикл:

 

нц для  i   от  1  до  N-1

         nMin:=  i

         нц для j от i+1 до N

             если A[j]<A[nMin] то

                  nMin:=j

             все

         кц

          если  i <>nMii то

                 gjvtyznmместами A[i]   и A[nMin]

           все

кц

 

«Быстрая сортировка»

Методы сортировки, описанные ранее, работают медленно для больших массивов данных (более 1000 элементов). Поэтому в середине XX века математики и программисты серьезно занимались разработкой более эффективных алгоритмов сортировки. Один из самых популярных «быстрых» алгоритмов, разработанный в 1960 г. английским учёным Чарльзом Хоаром, так и называется — «быстрая сортировка» (англ. quicksort).

Будем исходить из того, что сначала лучше делать перестановки элементов массива на большом расстоянии. Предположим, что у нас есть n элементов и известно, что они уже отсортированы в обратном порядке. Тогда за n/2 обменов можно отсортировать их как нужно — сначала поменять местами первый и последний, а затем последовательно двигаться с двух сторон к центру. Хотя это справедливо только тогда, когда порядок элементов обратный, подобная идея положена в основу алгоритма Quicksort.

Пусть дан массив А из п элементов. Выберем сначала наугад любой элемент массива (назовем его X). Обычно выбирают средний элемент массива, хотя это необязательно. На первом этапе мы расставим элементы так, что слева от некоторой границы находятся все числа, меньшие или равные X, а справа — большие или равные X:

Заметим, что элементы, равные X, могут находиться в обеих частях.

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

Лучше всего выбирать X так, чтобы в обеих частях было равное количество элементов. Такое значение X называется медианой массива. Однако для того, чтобы найти медиану, надо сначала отсортировать массив, т. е. заранее решить ту самую задачу, которую мы собираемся решить этим способом. Поэтому обычно в качестве X выбирают средний элемент массива.

Сначала будем просматривать массив слева до тех пор, пока не обнаружим элемент, который больше X (и, следовательно, должен стоять справа от X). Затем просматриваем массив справа до тех пор, пока не обнаружим элемент, меньший X (он должен стоять слева от X). Теперь поменяем местами эти два элемента и продолжим просмотр до тех пор, пока два «просмотра» не встретятся где-то в середине массива. В результате массив окажется разбитым на 2 части: левую со значениями, меньшими или равными X, и правую со значениями, большими или равными X. На этом первый этап («разделение») закончен. Затем такая же процедура применяется к обеим частям массива до тех пор, пока в каждой части не останется по одному элементу (таким образом, массив будет отсортирован).

 

Чтобы понять сущность метода, рассмотрим пример. Пусть задан массив:

 

Выберем в качестве X средний элемент массива, т. е. 67. Найдем первый слева элемент массива, который больше или равен X и должен стоять во второй части. Это число 78. Обозначим индекс этого элемента через L. Теперь находим самый правый элемент, который меньше X и должен стоять в первой части. Это число 34. Обозначим его индекс через R: Теперь поменяем местами эти два элемента. Сдвигая переменную L вправо, а R — влево, находим следующую пару, которую надо переставить. Это числа 82 и 44:Следующая пара элементов для перестановки — числа 67 и 55:

 

После этой перестановки дальнейший поиск приводит к тому, что переменная L становится больше R:

 

В результате все элементы массива, расположенные левее A[L] меньше или равны X, a все элементы A[R] больше или равны X.

Теперь нужно применить тот же алгоритм к двум частям массива: первая часть — с 1-го элемента до r-го элемента, а вторая часть -— с L-го до последнего элемента. Как вы знаете, такой приём называется рекурсией.

 

 

 

Чтобы не загромождать решение деталями оформления, которые сильно различаются в школьном алгоритмическом языке и в Паскале, предположим, что в нашей программе один глобальный массив А с индексами от 1 до N, который нужно сортировать. Термин «глобальный» означает, что массив доступен всем процедурам и функциям. Глобальные данные объявляются выше основной программы:

 

цел  N   =   5

целтаб А[1:Ы]

алг Быстрая сортировка

нач

 

 

кон

 

Тогда процедура сортировки принимает только два параметра, ограничивающие её «рабочую зону»: nStart — номер первого элемента, и nEnd — номер последнего элемента. Если nStart = nEnd, то в «рабочей зоне» один элемент и сортировка не требуется, т. е. нужно выйти из процедуры. В этом случае рекурсивные вызовы заканчиваются.

 

Приведём полностью процедуру быстрой сортировки на школьном алгоритмическом языке:

 

 

алг  qSort(цел   nStart,   nEnd)

нач

     цел   L,    R,    с,    X

    если nStart>=nEnd то выход

    все

    L :=nStart; R:=nEnd;

   X:=A[div(L+R, 2) ]

   нц пока L<=R | разделение

         нц пока A[L]<X; L:=L+1

         кц

         нц пока A[R]>X; R:=R-1

         кц

           если L<=R то

              c:=A[L];  A[L]:=A[R]; A[R]:=c

              L:=L+1; R:=R-1

           все

         кц

        qSort (nStart, R) | рекурсивные вызовы

        qSort(L, nEnd)

кон

 

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

 

qSort(l,   N)

 

Скорость работы быстрой сортировки зависит от того, насколько удачно выбирается вспомогательный элемент X. Самый лучший случай — когда на каждом этапе массив делится на две равные части. Худший случай — когда в одной части оказывается только один элемент, а в другой — все остальные. При этом глубина рекурсии достигает N, что может привести к переполнению стека (нехватке стековой памяти).

 

Для того чтобы уменьшить вероятность худшего случая, в алгоритм вводят случайность: в качестве X на каждом шаге выбирают не середину рабочей части массива, а элемент со случайным номером:

 

X:=A[irand(L,R)]

 

В таблице 8.1 сравнивается время сортировки (в секундах) массивов разного размера, заполненных случайными значениями, с использованием трёх изученных алгоритмов.

 

Таблица 8.1

 

 

 

Как  показывают  эти  данные,   преимущество  быстрой  сортировки становится подавляющим при увеличении N.

 

Вопросы и задания

1.         Что такое сортировка?

2.         На какой идее основан метод пузырька? Метод выбора?

3.         Объясните, зачем нужен вложенный цикл в описанных методах сортировки.

4.         Сравните на примере метод пузырька и метод выбора. Какой из них требует меньше перестановок?

5.         Расскажите про основные идеи метода «быстрой сортировки».

6.         Как нужно изменить приведённые в параграфе алгоритмы, чтобы элементы массива были отсортированы по убыванию?

7.         Как вы думаете, можно ли использовать метод «быстрой сортировки» для нечисловых данных, например для символьных строк?

8.         От чего зависит скорость «быстрой сортировки»? Какой самый лучший и самый худший случай?

9.         Как  вы думаете,   может ли  метод   «быстрой  сортировки»   работать дольше, чем метод выбора (или другой «простой» метод)? Если да, то при каких условиях?

 

Подготовьте сообщение

 

а)         «Сортировка вставкой»

б)         «Сортировка слиянием»

в)         «Сортировка списков на языке Python»