Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Свойства и классификация).pdf
Добавлен: 23.04.2023
Просмотров: 309
Скачиваний: 2
Глава 2. Примеры сортировок
2.1 Простой обмен (метод пузырька)
В простейшем случае задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В={K1, K2,..., Kn}. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'={K'1, K'2,...,K'n}, в котором для любого 1<=i<=n элемент K'i <= K'i+1.
Основной принцип пузырьковой сортировки - систематический обмен соседних элементов с неправильным порядком при просмотре всего списка слева направо. При этом максимальные элементы «выталкиваются», «всплывают» в конце списка. Если сравнить сортируемые элементы с пузырьками воздуха в воде, то возникает аналогия – максимальные значения «всплывают» на поверхность подобно пузырькам воздуха. Благодаря такой аналогии сортировка простым обменом получила название пузырьковой сортировки.
Работа алгоритма пузырьковой сортировки происходит по следующим шагам:
- Сравниваются 2 соседних элемента. Если они не являются упорядоченными, то происходит их обмен.
- Происходит переход к следующей паре элементов до тех пор, пока не дойдем до конца массива.
- Алгоритм совершает n-1 проходов по массиву, где n – количество элементов массива.
Пример: пусть задан исходный список B=<20,-5,10,8,7>. В результате «первого прохода» алгоритма число 20 переместится в конец списка:
|
Первый проход |
-5 20 10 8 7 |
|
-5 10 20 8 7 |
|
|
-5 10 8 20 7 |
|
|
-5 10 8 7 20 |
|
|
Второй проход |
-5 10 8 7 20 |
|
-5 8 10 7 20 |
|
|
-5 8 7 10 20 |
|
|
Третий проход |
-5 8 7 10 20 |
|
-5 7 8 10 20 |
|
|
Четвертый проход |
-5 7 8 10 20 |
Таблица 1. Пример работы сортировки пузырьком.
Блок-схема алгоритма пузырьковой сортировки выглядит следующим образом:
Рисунок 3. Блок-схема сортировки пузырьком.
Приведем код сортировки на языке С++:
#define SWAP(A, B) { int t = A; A = B; B = t; } // зададим функцию обмена
void bubblesort(int *a, int n) //сортировка пузырьком
{ int j, nn;
do {
nn = 0;
for (j = 1; j < n; ++j)
if (a[j - 1] > a[j]) {// если 2 соседних элемента не упорядочены
SWAP(a[j - 1], a[j]); // меняем их местами nn = j;
}
n = nn;
} while (n);
}
2.2 Простой выбор
Это наиболее естественный алгоритм упорядочивания. Допустим, что элементы K0 , ..., Ki-1 уже упорядочены, тогда среди оставшихся Ki , ..., Kn1 находим минимальный элемент и меняем его местами с i-тым элементом. И так далее, пока массив не будет полностью упорядочен. То есть сортировка выбором состоит в разделении исходного массива на две части, отсортированную и не отсортированную. Изначально отсортированная часть пуста. На каждой итерации алгоритма в неотсортированной части находится наименьший элемент, после чего он обменивается местами с первым элементом неотсортированой части, и этот первый элемент присоединяется к отсортированной части массива.
Пример: пусть задан исходный список B=<4,17,25,1,21,13,2>.
|
Первый проход |
1 17 25 4 21 13 2 |
|
Второй проход |
1 2 25 4 21 13 17 |
|
Третий проход |
1 2 4 25 21 13 17 |
|
Четвертый проход |
1 2 4 13 21 25 17 |
|
Пятый проход |
1 2 4 13 17 25 21 |
|
Шестой проход |
1 2 4 13 17 21 25 |
Таблица 2. Пример работы сортировки простым выбором.
Блок-схема алгоритма сортировки простым выбором выглядит следующим образом:
Рисунок 4. Блок-схема сортировки простым выбором.
Приведем код сортировки на языке С++:
void insertionSort(int *arrayPtr, int length) // сортировка вставками
{
int temp, // временная переменная для хранения значения элемента сортируемого
массива item; // индекс предыдущего элемента for (int counter = 1; counter < length; counter++) {
temp = arrayPtr[counter]; // инициализируем временную переменную текущим
значением элемента массива item = counter - 1; // запоминаем индекс предыдущего элемента массива while (item >= 0 && arrayPtr[item] > temp) // пока индекс не равен 0 и
предыдущий элемент массива больше текущего
|
{ |
||
|
массива |
arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов |
|
|
arrayPtr[item] = temp; |
||
|
item--; |
||
|
} } |
} |
|
2.3 Сортировка вставкой
Пусть 1 < j ≤ N и записи R1, ..., Rj-1 уже размещены так, что K1 ≤ K2 ≤...≤ Kj-1. Будем сравнивать по очереди Kj с Kj-1, Kj-2, ..., K1 до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri, и Ri+1. Тогда подвинем записи Ri+1, ... Rj-1 на одно место вверх и поместим новую запись в позицию i+1.
Сортировка вставками основана на том, что она сортирует список, формируя его заново – вставляя очередной элемент в нужное место уже отсортированного списка.
Пример: пусть задан исходный список B=<4,17,25,1,21,13,2>.
|
Первый проход |
4 17 25 1 21 13 2 |
|
Второй проход |
4 17 25 1 21 13 2 |
|
Третий проход |
1 4 17 25 21 13 2 |
|
Четвертый проход |
1 4 17 21 25 13 2 |
|
Пятый проход |
1 4 13 17 21 25 2 |
|
Шестой проход |
1 2 4 13 17 21 25 |
Таблица 3. Пример работы сортировки вставками.
Блок-схема алгоритма сортировки простым выбором выглядит следующим образом:
Рисунок 5. Блок-схема сортировки вставками.
Приведем код сортировки на языке С++:
void insertionSort(int *arrayPtr, int length) // сортировка вставками
{
int temp, // временная переменная для хранения значения элемента сортируемого
массива item; // индекс предыдущего элемента
for (int counter = 1; counter < length; counter++)
{
temp = arrayPtr[counter]; // инициализируем временную переменную текущим
значением элемента массива item = counter - 1; // запоминаем индекс предыдущего элемента массива while (item >= 0 && arrayPtr[item] > temp) // пока индекс не равен 0 и
предыдущий элемент массива больше текущего
|
{ |
||
|
массива |
arrayPtr[item + 1] = arrayPtr[item]; // перестановка элементов |
|
|
arrayPtr[item] = temp; |
||
|
item--; |
||
|
} |
} |
} |
2.4 Сортировка методом Шелла
Сортировка Шелла является усовершенствованным методом алгоритма сортировки простыми вставками. Характерным для данного метода является то, что сначала рассматриваются отдаленные, а затем близко расположенные элементы. Каждый проход в этом случае характеризуется некоторым смещением h для сортируемых элементов – это интервал, который разделяет сравниваемые элементы. Другими словами, каждый элемент отстоит от предыдущего на h позиций. Затем расстояние между сортируемыми элементами уменьшается. Для h часто используют последовательность 8,4,2,1. Однако это не единственно возможный вариант. Таким образом, единственной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.[8,9]
В качестве примера рассмотрим алгоритм сортировки массива a[0].. a[15].
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
Таблица 4. Исходный массив для сортировки Шелла.
Сначала сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
||||||||||||||
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
||||||||||||||
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
||||||||||||||
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
||||||||||||||
|
2 |
5 |
2 |
7 |
2 |
1 |
3 |
5 |
1 |
2 |
||||||||||||||
|
Таблица 4. Первый этап обработки данных. В результате получаем: |
|||||||||||||||||||||||
|
5 |
2 |
7 |
2 |
1 |
2 |
3 |
5 |
1 |
2 |
||||||||||||||
Таблица 5. Результат первого этапа.
Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).
|
5 |
2 |
7 |
2 |
1 |
2 |
3 |
5 |
1 |
2 |
||||||
|
5 |
2 |
7 |
2 |
1 |
2 |
3 |
5 |
1 |
2 |
||||||
|
5 |
2 |
7 |
2 |
1 |
2 |
3 |
5 |
1 |
2 |
||||||
|
5 |
2 |
7 |
2 |
1 |
2 |
3 |
5 |
1 |
2 |
Таблица 6. Второй этап обработки данных.
В результате получаем:
|
2 |
5 |
1 |
1 |
2 |
2 |
5 |
2 |
7 |
3 |
Таблица 7. Результат второго этапа.
Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).
|
2 |
5 |
1 |
1 |
2 |
2 |
5 |
2 |
7 |
3 |
||||||
|
2 |
5 |
1 |
1 |
2 |
2 |
5 |
2 |
7 |
3 |
Таблица 8. Третий этап обработки данных.
В результате получаем:
|
1 |
5 |
2 |
2 |
2 |
1 |
5 |
2 |
7 |
3 |
||||||
|
Таблица 9. Результат третьего этапа. На последнем шаге сортируем вставками все 16 элементов: |
|||||||||||||||
|
1 |
2 |
2 |
5 |
2 |
1 |
2 |
3 |
5 |
7 |
||||||
Таблица 10. Итоговый результат сортировки Шелла.
Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Но на самом деле предыдущие проходы продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.
Блок-схема алгоритма сортировки простым выбором выглядит следующим образом:
Рисунок 6. Блок-схема сортировки Шелла.
Приведем код сортировки на языке С++:
void ShellSort(int array[], int size) // * ∆k = (b∆k−1)/2 ∆0 = N
{
int step, i, j, temp;
for (step = size / 2; step > 0; step /= 2) { // разбиение на шаг for (i = step; i < size; i++) { // кол-во пар, которые надо
проверить for (j = 0; j < i; j++) { // проверка каждой пары if (array[j] > array[i]) { // если первое число в
паре больше второго, то поменять местами
temp = array[j]; array[j] = array[i];
array[i] = temp;
}
}
}
}
}
2.5 Быстрая сортировка
Шаги алгоритма:
- В алгоритме выбирается опорный элемент - некоторый элемент массива, относительно которого будет происходить разделение массива на части. Теоретически, то может быть любой элемент массива. Существуют разные стратегии выбора опорного элемента – например каждый раз выбирать средний элемент, или последний.
- Массив разделяется на 2 части – в одну часть идут все элементы меньшие или равные опорного, в другу часть все элементы большие опорного.
- Далее каждую из получившихся частей подвергаем быстрой сортировки. Таким образом, эта сортировка является рекурсивной. Условием выхода из рекурсии является получение на вход массива длиной в один или два элемента
- После окончания действия алгоритма массив будет отсортирован.