Данный метод также относится к классу простейших, но по сравнению с методом пузырька имеет немного лучшие показатели.
Пусть имеется n элементов а1 а2, а3,..., аn, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:
· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3,..., аi-1
· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2,..., аn
На шаге i для элемента аi находится подходящее место в уже отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости: сравниваем аi с аi-1, если аi < аi-1, то переставляем их, потом сравниваем аi-1 с аi-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор, пока не будет выполнено одно из 2-х следующих условий:
· в отсортированном наборе найден элемент, меньший аi (все остальные не просмотренные элементы будут еще меньше)
· достигнут первый элемент набора а1, что произойдет в том случае, если аi меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве
Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19
| а1 | а2 | а3 | а4 | а5 | а6 | Выполняемые операции | |
| шаг 2 | сравнение 15 и 33, обмена нет, 15 – пока первый | ||||||
| шаг 3 | сравнение 33 и 42, обмена нет, 15 и 33 пока первые | ||||||
| шаг 4 | сравнение 07 и 42, меняем их | ||||||
| сравнение 07 и 33, меняем их | |||||||
| сравнение 07 и 15, меняем их; 07-15-33 пока первые | |||||||
| шаг 5 | сравнение 12 и 42, меняем их | ||||||
| сравнение 12 и 33, меняем их | |||||||
| сравнение 12 и 15, меняем их | |||||||
| сравнение 12 и 07, обмена нет, пока: 07-12-15-33 | |||||||
| шаг 6 | сравнение 19 и 42, меняем их | ||||||
| сравнение 19 и 33, меняем их | |||||||
| сравнение 19 и 15, обмена нет, все готово |
Для данного примера было сделано 12 сравнений и 8 перестановок, что чуть лучше предыдущего метода. В среднем, число сравнений по данному методу примерно в 2 раза меньше, чем в методе пузырька, оставаясь тем не менее пропорциональным величине n2. Наилучший результат этот метод показывает для уже упорядоченного исходного массива – всего (n-1) сравнение.
Программная реализация включает два вложенных цикла, но в отличие от предыдущего метода, внутренний цикл реализуется как while-do с возможностью остановки при обнаружении меньшего элемента.
for i:= 2 to n do
Begin
temp:= a [i]; j:= i – 1;
While (j > 0) and (temp < a [j]) do
begin a [j+1]:= a [j]; j:= j – 1; end;
a [j+1]:= temp;
end;
Простейшие методы сортировки: метод выбора
Данный метод из группы простейших имеет лучшие характеристики по числу перестановок, хотя он, как и оба ранее рассмотренных метода, в целом имеет трудоемкость O(n2). Его чуть более лучшие показатели связаны с тем, что в некоторых ситуациях выполняется перестановка не соседних элементов, а отстоящих на некотором расстоянии друг от друга.
Пусть имеется n элементов а1 а2, а3,..., аn, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, пронумерованных от 1 до n-1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:
· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3,..., аi-1
· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2,..., аn
Суть метода состоит в том, что в необработанном наборе отыскивается наименьший элемент, который меняется местами с элементом аi. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.
Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19
| а1 | а2 | а3 | а4 | а5 | а6 | Выполняемые операции | |
| шаг 1 | сравнение 15 и 33, min = 15 | ||||||
| сравнение 15 и 42, min = 15 | |||||||
| сравнение 15 и 07, min = 07 | |||||||
| сравнение 07 и 12, min = 07 | |||||||
| сравнение 07 и 19, min = 07, обмен 15 и 07 | |||||||
| шаг 2 | сравнение 33 и 42, min = 33 | ||||||
| сравнение 33 и 15, min = 15 | |||||||
| сравнение 15 и 12, min = 12 | |||||||
| сравнение 12 и 19, min = 12, обмен 33 и 12 | |||||||
| шаг 3 | сравнение 42 и 15, min = 15 | ||||||
| сравнение 15 и 33, min = 15 | |||||||
| сравнение 15 и 19, min = 15, обмен 42 и 15 | |||||||
| шаг 4 | сравнение 42 и 33, min = 33 | ||||||
| сравнение 33 и 19, min = 19, обмен 42 и 19 | |||||||
| шаг 5 | сравнение 33 и 42, min = 33, обмена нет, все готово |
В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log 2 n)
Особенности программной реализации. Внешний цикл обрабатывает основные шаги и выполняет перестановку минимального элемента, а внутренний организует поиск наименьшего элемента в необработанной части массива
for i:= 1 to n–1 do
Begin
k:= i; temp:= a [i]; {устанавливаем начальный минимальный элемент}
for j:= i+1 to n do
if a [j] < temp then
begin {изменяем текущий минимальный элемент}
k:= j; temp:= a [j];
end;
a [k]:= a [i]; a [i]:= temp;
end;
Общее заключение по простейшим методам сортировки.
Метод обмена (пузырька) имеет единственное преимущество – нулевое число пересылок в случае, если исходный набор уже отсортирован в нужном порядке. В остальных случаях все его показатели пропорциональны n2.
Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n). Во всех остальных случаях его показатели пропорциональны n2, хотя что касается оценки среднего числа сравнений, то она чуть лучше, чем у других методов. Многочисленные эксперименты показывают, что метод вставок дает наименьшее время сортировки среди всех простейших методов.
Метод выбора, как это и следовало ожидать, имеет лучшие показатели по числу пересылок, особенно – для общего случая, где оценка О(n*log 2 n) заметно лучше оценки O(n2). Поэтому его можно рекомендовать к использованию из всех простейших методов в том случае, если именно число перестановок является наиболее важным.
Практическое задание
Реализовать программу, объединяющую простейшие методы сортировки массивов:
· сортировку обменом (метод пузырька)
· сортировку выбором
· сортировку вставками
Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и выводом этого массива на экран
Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение.
После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.
Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.
1.7. Контрольные вопросы по теме
1. В чем состоит задача выбора алгоритмов решения однотипных задач?
2. Какие критерии используются при выборе алгоритмов?
3. Как оценивается трудоемкость алгоритма?
4. Что такое О-нотация и для чего она используется?
5. Какие группы функций можно выделить с помощью О-нотации?
6. Какие рекомендации следует использовать при выборе алгоритмов с помощью О-нотации?
7. Что можно сказать о применимости алгоритмов класса О(2n) и О(n!)?
8. Как оценивается трудоемкость программы, использующей несколько взаимодействующих алгоритмов?
9. Как классифицируются методы сортировки?
10. Что такое внутренняя и внешняя сортировка и в чем состоят особенности этих задач?
11. В чем состоят особенности универсальных и специальных методов внутренней сортировки?
12. Какие основные методы сортировки относятся к универсальным и какую они имеют трудоемкость?
13. В чем состоит практическое значение изучения простейших методов сортировки?
14. Как классифицируются методы поиска?
15. В чем состоит суть метода сортировки обменом?
16. Какие шаги выполняет алгоритм сортировки обменом?
17. Как программно реализуется сортировка обменом?
18. В чем достоинства и недостатки метода сортировки обменом?
19. Приведите практический пример сортировки массива методом обмена.
20. В чем состоит суть метода сортировки вставками?
21. Какие шаги выполняет алгоритм сортировки вставками?
22. Как программно реализуется сортировка вставками?
23. В чем достоинства и недостатки метода сортировки вставками?
24. Приведите практический пример сортировки массива методом вставок.
25. В чем состоит суть метода сортировки выбором?
26. Какие шаги выполняет алгоритм сортировки выбором?
27. Как программно реализуется сортировка выбором?
28. В чем достоинства и недостатки метода сортировки выбором?
29. Приведите практический пример сортировки массива методом выбора.