Файл: Общие сведения об алгоритмах сортировки.pdf

Внутренняя сортировка является базовой для любого алгоритма внешней сортировки – отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.

Следует отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к носителям.

Классификация алгоритмов по поведению позволяет выделить квадратичные и субквадратичные, а также логарифмические и линейные алгоритмы.

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

• Сортировка выбором (SelectSort)
• Сортировка пузырьком (BubbleSort) и ее улучшения
• Сортировка простыми вставками (InsertSort)
• Cортировка Шелла (ShellSort)

Логарифмические и линейные алгоритмы

• Пирамидальная сортировка (HeapSort)
• Быстрая сортировка (QuickSort)
• Поразрядная сортировка (Radix sort)

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

Изображенный на рисунке 3 график иллюстрирует разницу в эффективности различных алгоритмов.

Рисунок 3. Скорость различных алгоритмов

• коричневая линия: сортировка пузырьком;
• синяя линия: шейкер-сортировка;
• розовая линия: сортировка выбором;
• желтая линия: сортировка вставками;
• голубая линия: сортировка вставками со сторожевым элементом;
• фиолетовая линия: сортировка Шелла.

Глава 2. Наиболее широко известные алгоритмы сортировки.

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

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массиве, не окажутся в надлежащем порядке (рис.4).

Рисунок 4. Алгоритм сортировки выбором

Анализ алгоритма прямым выбором

Число сравнений ключей С не зависит от порядка ключей:

C=½(n²-n).

Число перестановок минимально

M_min=3(n-1)

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

M_max= n²/4 +3(n-1),

если первоначально ключи располагаются в обратном порядке.

Среднее число пересылок

M_ср≈n(ln n + g),

Где g = 0,577216... — константа Эйлера.

Резюме: как правило, сортировка прямым выбором предпочтительнее алгоритму прямого включения, однако, если ключи в начале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым.

void selectionSort(int data[], int lenD)

{

int j = 0;

int tmp = 0;

for(int i=0; i<lenD; i++){

j = i;

for(int k = i; k<lenD; k++){

if(data[j]>data[k]){

j = k;

}

}

tmp = data[i];

data[i] = data[j];

data[j] = tmp;

}

}

Пузырьковая сортировка (Bubble sort)

При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сравниваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива (рис.5).

Рисунок 5. Алгоритм сортировки пузырьком

void bubbleSort(int data[], int lenD)

{

int tmp = 0;

for(int i = 0;i<lenD;i++){

for(int j = (lenD-1);j>=(i+1);j--){

if(data[j]<data[j-1]){

tmp = data[j];

data[j]=data[j-1];

data[j-1]=tmp;

}

}

}

}

Анализ алгоритма

Число сравнений в алгоритме прямого обмена

С = (n² - n)/2,

а минимальное, среднее и максимальное число перемещений элементов равно соответственно

M_min = 0,

M_ср = 3(n² - n)/2,

M_max = 3(n² - n)/4.

Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.

Сортировка вставками (Insertion sort)

При сортировке вставками массив разбивается на две области: упорядоченную и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.

На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.

Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i] (рис.6).

Рисунок 6. Алгоритм сортировки вставками

Анализ выполнения

Число сравнений ключей C_i при i-м просеивании составляет самое большое i-1, самое меньшее – 1. Если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – i/2. Число пересылок

M_i = C_i+2.

Поэтому общее число сравнений и пересылок таковы:

C_min=n-1; M_min=3(n-1);

C_ср=(n²+n-2)/4; M_ср=(n²+9n-10)/4;

C_max=(n²+n-4)/4; M_max=(n²+3n-4)/2.

Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие оценки — когда элементы первоначально расположены в обратном порядке.

Резюме: сортировка методом прямого включения – не очень подходящий метод для компьютера, поскольку включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.

void insertionSort(int data[], int lenD)

{

int key = 0;

int i = 0;

for(int j = 1;j<lenD;j++){

key = data[j];

i = j-1;

while(i>=0 && data[i]>key){

data[i+1] = data[i];

i = i-1;

data[i+1]=key;

}

}

}

Сортировка слиянием (Merge sort)

При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.

Исходный массив приведен на рис.6.

Рисунок 6. Алгоритм сортировки слиянием

Разделим его пополам (рис.7).

Рисунок 7. Алгоритм сортировки слиянием

И будем делить каждую часть пополам, пока не останутся части с одним элементом (рис.8).

Рисунок 8. Алгоритм сортировки слиянием

Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив (рис.9).

Рисунок 9. Алгоритм сортировки слиянием

Сортировка слиянием во многом похожа на метод быстрой сортировки.  Производительность сортировки слиянием лежит между производительностью пирамидальной и быстрой сортировки. Но в отличие от пирамидальной и быстрой сортировок, метод сортировки слиянием ведет себя стабильно, поскольку он не зависит от перестановок элементов в массиве.

Еще одним достоинством сортировки слиянием является то, что он удобен для структур с последовательным доступом к элементам, таким как файлы на внешнем устройстве или связные списки. Этот метод, прежде всего, используется для внешней сортировки.

Недостатки метода заключаются в том, что он требует дополнительной памяти по объему равной объему сортируемого файла. Поэтому для больших файлов проблематично организовать сортировку слиянием в оперативной памяти.

В случаях, когда гарантированное время сортировки важно и размещение в оперативной памяти, возможно, следует предпочесть метод сортировки слиянием.

Для работы алгоритма мы должны реализовать следующие операции:

void mergeSort(int data[], int lenD)

{

if(lenD>1){

int middle = lenD/2;

int rem = lenD-middle;

int* L = new int[middle];

int* R = new int[rem];

for(int i=0;i<lenD;i++){

if(i<middle){

L[i] = data[i];

}

else{

R[i-middle] = data[i];

}

}

mergeSort(L,middle);

mergeSort(R,rem);

merge(data, lenD, L, middle, R, rem);

}

}

void merge(int merged[], int lenD, int L[], int lenL, int R[], int lenR){

int i = 0;

int j = 0;

while(i<lenL||j<lenR){

if (i<lenL & j<lenR){

if(L[i]<=R[j]){

merged[i+j] = L[i];

i++;

}

else{

merged[i+j] = R[j];

j++;

}

}

else if(i<lenL){

merged[i+j] = L[i];

i++;

}

else if(j<lenR){

merged[i+j] = R[j];

j++;

}

}

}

Быстрая сортировка (Quick sort)

Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения исходного массива на две области. Эти части находятся слева и справа от отмеченного элемента, называемого опорным. В конце процесса одна часть будет содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше опорного (рис.10).

Рисунок 10. Алгоритм быстрой сортировки

void quickSort(int* data, int const len)

{

int const lenD = len;

int pivot = 0;

int ind = lenD/2;

int i,j = 0,k = 0;

if(lenD>1){

int* L = new int[lenD];

int* R = new int[lenD];

pivot = data[ind];

for(i=0;i<lenD;i++){

if(i!=ind){

if(data[i]<pivot){

L[j] = data[i];

j++;

}

else{

R[k] = data[i];

k++;

}

}

}

quickSort(L,j);

quickSort(R,k);

for(int cnt=0;cnt<lenD;cnt++){

if(cnt<j){

data[cnt] = L[cnt];;

}

else if(cnt==j){

data[cnt] = pivot;

}

else{

data[cnt] = R[cnt-(j+1)];

}

}

}

}

Глава 3. Решение задачи.

Для подтверждения полученных компетенций была спроектирована программа на языке С++, которая демонстрирует работу всех перечисленных алгоритмов сортировки и позволяет проанализировать количество проходов и перестановок элементов для каждого алгоритма.

Для удобства работы в программе предусмотрено меню, которое позволяет выбрать любой алгоритм, а также заполнить массив случайными числами, чтобы убедиться, какой алгоритм наиболее эффективен на отсортированном и неотсортированном массивах.

while (true)

{

cout << "Выберите действие: " << endl;

cout << "1 - Сортировка выбором(Selection sort) " << endl;

cout << "2 - Пузырьковая сортировка(Bubble sort) " << endl;

cout << "3 - Сортировка вставками(Insertion sort) " << endl;

cout << "4 - Сортировка слиянием(Merge sort) " << endl;

cout << "5 - Быстрая сортировка(Quick sort) " << endl;

cout << "6 - Заполнение массива случайными числами " << endl;

cout << "0 - Выход " << endl;

int otvet;

cin >> otvet;

switch(otvet)

{

case 0: exit(0);

case 1: clearPr(); selectionSort(); print(); break;

case 2: clearPr(); bubbleSort(); print(); break;

case 3: clearPr(); insertionSort(); print(); break;

case 4: clearPr(); mergeSort(m, SIZE_M); print(); break;

case 5: clearPr(); quickSort(m, SIZE_M); print(); break;

case 9: create_m(); print(); break;

}

}

Ниже приведены результаты выполнения программы на массиве из 100 элементов.

Сортировка выбором – один из самых медленных алгоритмов, количество проходов по массиву в этом случае максимальное (рис.11)

Рисунок 11. Скриншот сортировки выбором

Однако, при полностью отсортированном массиве сортировка выбором не выполняет излишних перестановок, что говорит об устойчивости алгоритма (рис.12).

Рисунок 12. Скриншот сортировки выбором уже отсортированного массива

Количество проходов при сортировке пузырьковым методом ненамного меньше, зато значительно выше число перестановок (рис.13).