Практическая работа № 2. Реализация сортировки в массиве.
Объём учебного времени – 2ч
Методические рекомендации
1. Цель работы: Научиться применять алгоритмы сортировки массивов
2. Перечень необходимых средств обучения:
2.1 Технические средства обучения:
Компьютер Core i3 3.0, 2 Gb оперативной памяти, винчестер 250 Gb, DVD
2.2 Программное обеспечение:
- Программа ОС Windows XP/7;
- Антивирусные программы: Kaspersky AntiVirus;
- Браузер Internet Explorer;
- Интегрированная среда программирования MS Visual Studio 2010.
3. Основные теоретические положения:
Методы простой сортировки
Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки.
Сортировка простым выбором.
Рассмотрим идею на примере. Пусть исходный массив А состоит из 10 элементов: 5 13 7 9 1 8 16 4 10 2. После сортировки массив должен выглядеть так: 1 2 4 5 7 8 9 10 13 16.
Процесс сортировки выполняется следующим образом: максимальный элемент текущей части массива меняется местами с последним элементом. При этом длина отсортированной части увеличивается.
Количество сравнений. При первом просмотре N-1, при втором – N-2, при последнем – 1. Общее количество С=N-1+N-2+1= N* (N-1)/2 (сумма элементов арифметической прогрессии) или C=O (N2).
Сортировка простым обменом.
Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов: 5 4 8 2 9. Длина текущей части массива – N-k+1, где k - номер просмотра, I – номер первого элемента проверяемой пары, номер последней пары – N-k.
Первый просмотр: рассматривается весь массив.
I=1 5 4 8 2 9
> меняем
I=2 4 5 8 2 9
< не меняем
I=3 4 5 8 2 9
> меняем
I=4 4 5 2 8 9
< не меняем
9 находится на своем месте.
Второй просмотр: рассматриваем часть массива с первого до предпоследнего элемента.
I=1 4 5 2 8 9
< не меняем
I=2 4 5 2 8 9
> меняем
I=3 4 2 5 8 9
< не меняем
8 – на своем месте.
Третий просмотр: рассматриваемая часть массива содержит три первых элемента.
I=1 4 2 5 8 9
> меняем
I=2 2 4 5 8 9
< не меняем
5 – на своем месте.
Четвертый просмотр: рассматриваем последнюю пару элементов.
I=1 2 4 5 8 9
< не меняем
4 – на своем месте. Наименьший элемент – 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1.
Итак, наш массив отсортирован. Этот метод также называют методом «пузырька». Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более «легкие» элементы (элементы с заданным свойством) мало-помалу всплывают на «поверхность».
При сортировке методом «пузырька» выполняется N-1 просмотров, на каждом i-просмотре производится N-I сравнений. Общее количество С равно N* (N-1)/2, или O (N2).
Сортировка простыми вставками.
Сортировка этим методом производится последовательно шаг за шагом. На i-ом шаге считается, что часть массива, содержащая первые i-1 элементов, уже упорядочена, то есть A[1]≤A[2]≤…≤A[i-1]. Далее берется i-й элемент, и для него подбирается место в отсортированной части массива, такое, что после его вставки упорядоченность не нарушается, то есть требуется найти такое j (0≤j≤i-1), что A[j]≤A[i]<A[j+1] (при j=0 происходит только одно сравнение, если не использовать «барьерную» технику). Затем выполняется вставка элемента A[i] на место j. На каждом шаге отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить N-1 шаг.
Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию.
| 1-й шаг. 2-й шаг. 3-й шаг. 4-й шаг. 5-й шаг. 6-й шаг. 7-й шаг. 8-й шаг. 9-й шаг. | 13 6 8 11 3 1 5 9 15 7 6 13 8 11 3 1 5 9 15 7 6 8 13 11 3 1 5 9 15 7 6 8 11 13 3 1 5 9 15 7 3 6 8 11 13 1 5 9 15 7 1 3 6 8 11 13 5 9 15 7 1 3 5 6 8 11 13 9 15 7 1 3 5 6 8 9 11 13 15 7 1 3 5 6 8 9 11 13 15 7 1 3 5 6 7 8 9 11 13 15 | Рассматриваем часть массива из одного элемента 13. Вставляем второй элемент массива 6 так, чтобы упорядоченность сохранилась. Так как 6<13, записываем 6 на первое место. Отсортированная часть массива содержит два элемента (6 13). Возьмем третий элемент массива 8 и подберем для него место в упорядоченной части массива. 8>6 и 8<13, следовательно, его место второе. Следующий элемент – 11. Он записывается в упорядоченную часть массива на третье место, так как 11>8, но 11<13. Далее, действуя аналогичным образом, определяем, что 3 необходимо записать на первое место. По той же причине 1 записываем на первое место. Так как 5>3, но 5<6, то место 5 в упорядоченной части – третье. Место числа 9 – шестое. Определяем место для предпоследнего элемента 15. оказывается, что этот элемент массива уже находится на своем месте. Осталось подобрать подходящее место для последнего элемента 7. Массив отсортирован полностью. |
Оценим эффективность метода. Для массива, например, 1 2 3 4 5 6 7 8 потребуется N-1 сравнение (напомним, что мы сортируем в порядке возрастания), а для массива 8 7 6 5 4 3 2 1 – N*(N-1)/2 или C=O (N2).
Сортировка подсчетом. Пусть дан массив (А) из 10 элементов: 10, 5, 11, -5, 1, -4, 13, 12, -4, 13. Возьмем первый элемент, он больше пяти элементов. Запишем 5 в дополнительный массив счетчиков (Count). Выполним эту операцию для всех элементов массива А. В массиве Count имеем: 5, 4, 6, 0, 3, 1, 8, 7, 2, 9. Если разрешается использовать дополнительный массив для хранения отсортированных данных, то остается переписать каждый элемент исходного массива на соответствующее место в результирующем массиве (В).