Алгоритмы сортировки(23-32)
23. Характеристика:
1) Время сортировки – быстродействие алгоритма
2) Память под использование промежуточных данных
3) Устойчивость (сортировка, не меняющая взаимного расположения равных эл-тов наз-ся устойчивой)
4) Естественность поведения – эффективность при обработке уже отсортированных или частично отсортированных данных
5) Сфера применения алгоритма
Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" осталось прежним: элемент с полем "a", затем - с "b", затем - с "c".
Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" изменилось.
Сортировка с помощью включения (вставки)
Элементы мысленно делятся на уже готовую последовательность (от a0 до ai) и исходную. На каждом шаге, начиная с первого, i увеличивается на 1, из исходн.последовательности извлекается i-ый эл-т и перекладывается в готовую послед-ть, при этом он вставл-ся на нужное место.
i = 1 44 55 12 42 94 18 06 67
i = 2 44 55 12 42 94 18 06 67
i = 3 12 44 55 42 94 18 06 67
i = 4 12 42 44 55 94 18 06 67
i = 5 12 42 44 55 94 18 06 67
i = 6 12 18 42 44 55 94 06 67
i = 7 06 12 18 42 44 55 94 67
i = 8 06 12 18 42 44 55 67 94
Вставка эл-та на очередн.шаге осуществляется путем последовательных сравнений с эл-том, стоящим перед ним. В зависимости от результата сравнения эл-т остается либо на текущем месте (вставка завершена), либо эл-ты меняются местами, и процесс повторяется.
void insertSort(int* a, long size) { int x;long i, j;for(i =0; i < size; i++) // цикл проходов, i - номер прохода { x = a[i]; // поиск места элемента в готовой последовательности for (j = i-1; j >= 0 && a[j] > x; j--) a[j+1] = a[j]; //сдвигаем элемент направо, пока не дошли a[j+1] = x; // место найдено, вставить элемент } }Сортировка с помощью выделения (прямого выбора)
Описание:
1) Выбирается min-ый эл-т
2) Он меняется местами с 1-ым эл-том
3) Этот процесс повторяется с оставшимися элементами
void selectSort(int* a, long size)
{ int x, minE, minP;long i, j;for(i=0; i < size; i++) { цикл проходов, i-номер прохода x = a[i]; minE = 0x7fffffff; // поиск в остатке минимального элемента и его местаfor(j = i; j < size; j++) if(a[j] < minE) { minE = a[j]; minP = j; } // место мин найдено, переписываем мин элемент на i-ое место a[i] = minE; a[minP] = x;// на место мин записываем элемент a[i] }Сортировка с помощью обменов (пузырьковая сортировка)
Идея: проход снизу вверх по массиву. По пути просматриваются пары соседних эл-тов. Если эл-ты некоторой пары наход-ся в неправильном порядке, они меняются местами.
Следующий проход делается до второго сверху эл-та и т.д, проходы по уменьшающейся нижней части делаются до тех пор, пока там не останется один эл-т
void bubbleSort(int a[], long size) {long i, j;int x;for(i = 0; i < size; i++) { // i - номер проходаfor(j = size-1; j > i; j--) { // внутренний цикл прохода if (a[j-1] > a[j]) { x=a[j-1]; a[j-1]=a[j]; a[j]=x; } } }}27. Шейкерная сортировка
Для улучшения пузырьк.сортировки можно запоминать были ли перестановки в процессе последн.прохода. Если нет, заканчивать работу.
Это улучшение можно еще улучшить, если запомнить не только сам факт обмена, но и индекс последнего обмена.
Все пары соседних эл-тов выше этого индекса находятся в желаемом порядке, поэтому просмотры можно заканчивать на этом индексе, а не идти до заранее определенного нижнего предела.
Анализируя алгоритм, можно заметить некоторую асимметрию: всплывает пузырек сразу за один проход, а тонет очень медленно на одну позицию за проход. Поэтому появляется идея третьего улучшения: чередовать направление последовательных просмотров (сначала min вверх, а max вниз)
28. Сортировка Шелла
В 1959г. Шелл усовершенствовал сортировку вставкой.
Сначала отдельно группируются и сортируются эл-ты отстоящие друг от друга на 4.
44 55 12 42 94 18 06 67
44 18 06 42 94 55 12 67
На втором шаге перегруппироваются группы отстоящие друг от друга на две позиции
06 18 12 42 44 55 94 67
На последнем шаге обычная сортировка включением
06 12 18 42 44 55 67 94
Задан массив a[0].. a[15]
1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8]), (a[1], a[9]),...,
(a[7], a[15])
2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]),..., (a[3], a[7], a[11], a[15])
В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.
3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14])0
4. В конце сортируем вставками все 16 элементов
void shellSort(long* a, long size)
{long inc, i, j, seq[40];int s; // вычисление последовательности приращенийs = increment(seq, size);while (s >= 0) { // сортировка вставками с инкрементами inc[] inc = seq[s--]; for (i = inc; i < size; i++) { long temp = a[i]; for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc) a[j+inc] = a[j]; a[j+inc] = temp; } }}