Сортировка пузырьком
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
Код C++
| 123456789101112131415 | template<class T>void bubbleSort(T a[], long size) { long i, j; T 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; } }}} |
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.
Сортировка вставками
Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Код C++
| 12345678910111213141516 | templatevoid insertSort(T a[], long size) { T 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; }} |
Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как Theta(n2), дополнительная память при этом не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.
Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить их в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива.
|
|
Код C++
| 123456789101112131415161718192021222324252627 | // сортировка вставками со сторожевым элементомtemplateinline void insertSortGuarded(T a[], long size) {T x;long i, j;T backup = a[0]; // сохранить старый первый элемент setMin(a[0]); // заменить на минимальный // отсортировать массивfor (i=1; i < size; i++) {x = a[i]; for (j=i-1; a[j] > x; j--)a[j+1] = a[j];a[j+1] = x;} // вставить backup на правильное местоfor (j=1; j< backup; j++)a[j-1] = a[j]; // вставка элементаa[j-1] = backup;} |
Функция setmin(T& x) должна быть создана пользователем. Она заменяет x на элемент, заведомо меньший (меньший или равный, если говорить точнее) всех элементов массива.
Сортировка Шелла
Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Код C++
| 123456789101112131415161718192021222324252627282930313233343536373839 | int increment(long inc[], long size) { int p1, p2, p3, s; p1 = p2 = p3 = 1; s = -1; do { if (++s % 2) { inc[s] = 8*p1 - 6*p2 + 1; } else { inc[s] = 9*p1 - 9*p3 + 1; p2 *= 2; p3 *= 2; } p1 *= 2; } while(3*inc[s] < size); return s > 0? --s: 0;} templatevoid shellSort(T 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++) { T temp = a[i]; for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc) a[j+inc] = a[j]; a[j] = temp; } }} |
Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size.
Пирамидальная сортировка
Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).
|
|
Код C++
| 1234567891011121314151617181920212223242526272829303132333435363738394041 | templatevoid downHeap(T a[], long k, long n) { // процедура просеивания следующего элемента // До процедуры: a[k+1]...a[n] - пирамида // После: a[k]...a[n] - пирамида T new_elem; long child; new_elem = a[k]; while(k <= n/2) { // пока у a[k] есть дети child = 2*k; // выбираем большего сына if(child < n && a[child] < a[child+1]) child++; if(new_elem >= a[child]) break; // иначе a[k] = a[child]; // переносим сына наверх k = child; } a[k] = new_elem;} templatevoid heapSort(T a[], long size) { long i; T temp; // строим пирамиду for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1); // теперь a[0]...a[size-1] пирамида for(i=size-1; i > 0; i--) { // меняем первый с последним temp=a[i]; a[i]=a[0]; a[0]=temp; // восстанавливаем пирамидальность a[0]...a[i-1] downHeap(a, 0, i-1); }} |
Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.
Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.
Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.
Быстрая сортировка (сортировка Хоара)
"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.
Псевдокод.
Код
| 12345678910 | quickSort (массив a, верхняя граница N) {Выбрать опорный элемент p - середину массиваРазделить массив по этому элементуЕсли подмассив слева от p содержит более одного элемента,вызвать quickSort для него.Если подмассив справа от p содержит более одного элемента,вызвать quickSort для него.} |
|
|
Реализация на Си
Код C++
| 1234567891011121314151617181920212223242526 | template<class T>void quickSortR(T* a, long N) {// На входе - массив a[], a[N] - его последний элемент. long i = 0, j = N; // поставить указатели на исходные места T temp, p; p = a[ N>>1 ]; // центральный элемент // процедура разделения do { while (a[i] < p) i++; while (a[j] > p) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i<=j); // рекурсивные вызовы, если есть, что сортировать if (j > 0) quickSortR(a, j); if (N > i) quickSortR(a+i, N-i);} |
Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.
Итеративный алгоритм быстрой сортировки.
Псевдокод.
Код
| 12345678910111213 | Итеративная QuickSort (массив a, размер size) {Положить в стек запрос на сортировку массива от 0 до size-1.do {Взять границы lb и ub текущего массива из стека.do {1. Произвести операцию разделения над текущим массивом a[lb..ub].2. Отправить границы большей из получившихся частей в стек.3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.} пока меньшая часть состоит из двух или более элементов} пока в стеке есть запросы} |
Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стекаtemplate<class T>void qSortI(T a[], long size) { long i, j; // указатели, участвующие в разделенииlong lb, ub; // границы сортируемого в цикле фрагмента long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов// каждый запрос задается парой значений,// а именно: левой(lbstack) и правой(ubstack)// границами промежуткаlong stackpos = 1; // текущая позиция стекаlong ppos; // середина массиваT pivot; // опорный элементT temp; lbstack[1] = 0;ubstack[1] = size-1; do {// Взять границы lb и ub текущего массива из стека.lb = lbstack[ stackpos ];ub = ubstack[ stackpos ];stackpos--; do {// Шаг 1. Разделение по элементу pivotppos = (lb + ub) >> 1;i = lb; j = ub; pivot = a[ppos];do {while (a[i] < pivot) i++;while (pivot < a[j]) j--;if (i <= j) {temp = a[i]; a[i] = a[j]; a[j] = temp;i++; j--;}} while (i <= j); // Сейчас указатель i указывает на начало правого подмассива,// j - на конец левого (см. иллюстрацию выше), lb? j? i? ub.// Возможен случай, когда указатель i или j выходит за границу массива // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ubif (i < ppos) { // правая часть большеif (i < ub) { // если в ней больше 1 элемента - нужноstackpos++; // сортировать, запрос в стекlbstack[ stackpos ] = i;ubstack[ stackpos ] = ub;}ub = j; // следующая итерация разделения// будет работать с левой частью} else { // левая часть большеif (j > lb) {stackpos++;lbstack[ stackpos ] = lb;ubstack[ stackpos ] = j;}lb = i;}} while (lb < ub); // пока в меньшей части более 1 элемента} while (stackpos!= 0); // пока есть запросы в стеке}
Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.
Поразрядная сортировка
Рассматриваемый ниже алгоритм существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
Код C++
| 1234567891011121314151617181920212223242526272829303132333435363738394041 | typedef struct slist_ { long val; struct slist_ *next; } slist; // функция сортировки возвращает указатель на начало отсортированного списка slist *radix_list(slist *l, int t) { // t - разрядность (максимальная длина числа) int i, j, d, m=1; slist *temp, *out, *head[10], *tail[10]; out=l; for (j=1; j<=t; j++) { for (i=0; i<=9; i++) head[i] = (tail[i]=NULL); while (l!= NULL) { d = ((int)(l->val/m))%(int)10; temp = tail[d]; if (head[d]==NULL) head[d] = l; else temp->next = l; temp = tail[d] = l; l = l->next; temp->next = NULL; } for (i=0; i<=9; i++) if (head[i]!= NULL) break; l = head[i]; temp = tail[i]; for (d=i+1; d<=9; d++) { if (head[d]!= NULL) { temp->next = head[d]; temp = tail[d]; } } m*=10; } return (out);} |