Кроме того, доступ к данным на носителе производится намного

Медленнее, чем операции с оперативной памятью.

Данный класс алгоритмов делится на два основных подкласса:

Внутренняя сортировка оперирует с массивами, целиком

Помещающимися в оперативной памяти с произвольным доступом к

Любой ячейке. Данные обычно сортируются на том же месте, без

Дополнительных затрат.

Внешняя сортировка оперирует с запоминающими устройствами

Большого объема, но с доступом не произвольным, а

Последовательным (сортировка файлов), т.е в данный момент мы

'видим' только один элемент, а затраты на перемотку по сравнению с

Памятью неоправданно велики. Это приводит к специальным методам

Сортировки, обычно использующим дополнительное дисковое

Пространство.

Основные методы сортировки

Статьи ниже являются частями одной большой, так что в

Последующих может использоваться информация из предыдущих. В

программах используются переопределения:

Typedef double real;

Typedef unsigned long ulong;

Typedef unsigned short ushort;

Typedef unsigned char uchar;

Под переменной size принимается количество элементов в массиве, а

Для обозначения индекса последнего элемента используется N.

Очевидно, size=N+1.

Квадратичные и субквадратичные алгоритмы

Сортировка выбором(SelectSort)

Сортировка пузырьком(BubbleSort) и ее улучшения

Сортировка простыми вставками(InsertSort)

Cортировка Шелла (ShellSort)

Сравнение времени сортировок

14. 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;

}

}

}

}

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i. Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерациюtemplate<class T>

void shakerSort(T a[], long size) {

long j, k = size-1;

long lb=1, ub = size-1; // границы неотсортированной части массива

T x;

do {

// проход снизу вверх

for(j=ub; j>0; j--) {

if (a[j-1] > a[j]) {

x=a[j-1]; a[j-1]=a[j]; a[j]=x;

k=j;

}

}

lb = k+1;

// проход сверху вниз

for (j=1; j<=ub; j++) {

if (a[j-1] > a[j]) {

x=a[j-1]; a[j-1]=a[j]; a[j]=x;

k=j;

}

}

ub = k-1;

} while (lb < ub);

}

дея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i]... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже. template<class T>

void selectSort(T a[], long size) {

Long i, j, k;

T x;

for(i=0; i < size; i++) { // i - номер текущего шага

k=i; x=a[i];

for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента

if (a[j] < x) {

k=j; x=a[j]; // k - индекс наименьшего элемента

}

a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]

}

}