Оцінка складності алгоритму . 21

У i-му проході обробляється підмасив А[0]-A[i] і вимагає в середньому i/2 порівнянь. Загальне число порівнянь становить

1/2 + 2/2 + 3/2 + ... + (N-2) / 2 + (n-l) / 2 = n (n-l) / 4

// Впорядкування n-елементного масиву типу Т,

// представлення алгоритму сортування методом гібридного вибору

template<classT>

void SelectionSort(T A[], int n)

{

// індекс найменшого елемента на кожному проході

int smalllndex;

int i, j;

for (i=0; i<n-l; i++)

{

// почати прохід з індексу i; встановити smalllndex в i

smalllndex =i;

for (j=i+l; j<n; j++)

// оновити smalllndex, якщо знайдений менший елемент

if (Alj] < A[smalllndex])

smalllndex = j;

//по закінченні помістити найменший елемент в A [i] 22

Swap(A[i], A[smalllndex]);

}

}

// Представлення алгоритму сортування методом бульбашки.

// BubbleSort приймає масив А і його розмір – n.

// Сортування виконується за допомогою низки проходів, поки lastExchangelndex = 0.

template<classT>

void BubbleSort (T А[], int n)

{

int i, j;

// Індекс останнього елемента, що брав участь в обміні

int lastExchangelndex;

// i - Індекс останнього елемента в підсписку i = п-1;

// продовжувати процес, поки не буде зроблено жодного обміну

while (і > 0)

{

// Початкове значення lastExchangelndex lastExchangelndex = 0;

// Сканувати підсписок A [0] - A [i]

for (j=0; j < i; j++)

// змінити місця сусідніх елеменів і оновити lastExchangelndex 23

If(A[j+l] < A[j])

{

Swap(A[j], A[j+1]);

lastExchangelndex = j;

}

//присвоїти i значення індексу останнього обміну, продовжити сортування

i = lastExchangelndex;

}

}

// Сортування вставками впорядковує підсписки A [0] ... A [i],

// 1 <= i <= n-1. Для кожного i A [i] вставляється в підходящу

// позиціюА [j]

template<class T>

void InsertionSort(T A[], int n)

{

int i, j;

T temp;

// і визначає підсписок А [0] ... A [i]

for (i=l; i<n; i++) 24

{

// Індекс j пробігає вниз за списком від A [i] в процесі

// пошуку правильної позиції вставленого значення j = i;

temp = A[i] ;

//виявити відповідну позицію для вставки, скануючи подспісок,

// поки temp <A [j-1] або поки не дістанеться початок списку

while (j> 0 && temp<A[j-1])

{

// зсунути елементи вправо, щоб звільнити місце для вставки

A[j] = A[j-1];

j--;

}

// точка вставки знайдена; вставити temp

A[j] = temp;

}

}

Порівняння часу сортування за методами

А = 800, 150, 300, 600, 550, 650, 400, 350, 450, 700 20

A [mid] = 550, Індекси - зміні scanUp = 0, scanDown = 9.

Оцінка складності алгоритму швидкого сортування О(n log₂n)

При першому скануванні проводиться n-1 порівнянь. В результатістворюються два підсписки розміром n / 2. На наступній фазі обробка кожного підсписку вимагає приблизно n / 2 порівнянь. Загальне число порівнянь на ційфазі дорівнює 2 (n / 2) = n. На наступній фазі обробляються чотири підсписки, що вимагає 4 (n / 4) порівнянь, і т.д. Зрештою процес розбиття припиняється після к проходів, коли підсписки містять поодному елементу. Загальне число порівнянь приблизно однакове

n + 2(n/2) + 4(n/4) + ... + n(n/n) = n + n+... + n = n*k = n* log₂n

// Quicksort приймає у якості параметрів масив 22

// та граничні значення його індексів

template <class T>

void Quicksort(T A[], int low, int high)

{

// локальні змінні, що містять індекс середини mid,

// центральний елементтаіндекси сканування

t pivot;

int scanUp, scanDown;

int mid;

// якщо діапазон індексів не включає в себе як мінімум два елементи, повернутися

if (high - low <= 0)

return;

else

/ / Якщо в підсписку два елементи, порівняти їх між собою

/ / І поміняти місцями при необхідності

if (high - low == 1)

{

if (A[high] < A[low])

Swap(A[low], Afhigh]);

return; 23

}

/ / Отримати індекс середини і присвоїти визначене їм значення

/ / Центральному значеннює

mid = (low + high)/2;

pivot = A[mid];

/ / Поміняти місцями центральний і початковий елементи списку

/ / І ініціалізувати індекси scanUp і scanDown

Swap (A[mid], A[low]);

scanUp = low + 1;

scanDown = high;

/ / Шукати елементи, розташовані не в тих підсписках.

/ / Зупинитися при scanDown <scanUp

do

{

/ / Просуватися вгору по нижньому підсписку; зупинитися,

/ / Коли scanUp вкаже на верхній підсписок або якщо

/ / Вказуваний цим індексом елемент> центрального

while (scanUp <= scanDown && A[scanUp] <= pivot)

scanUp++;

/ / Просуватися вниз по верхньому підсписку; зупинитися,

/ / Якщо scanDown вкаже елемент <= центрального. 24

/ / Зупинка на елементі A [low] гарантується

while (pivot < A[scanDown])

scanDown--;

/ / Якщо індекси все ще у своїх підсписках, то вони вказують

/ / Два елементи, що знаходяться не в тих підсписках.

/ / Поміняти їх місцямиif (scanUp < scanDown)

{

Swap (AfscanUp], AEscanDown]);

}

}

while (scanUp < scanDown);

/ / Копіювати центральний елемент в точку розбиття

A[low] = A[scanDown];

A[scanDown] = pivot;

/ / Якщо нижній підсписок (low. .. scanDown-1) має 2 або більше

/ / елементів, виконати рекурсивний виклик

if (low < scanDown-1)

Quicksort(A, low, scanDown-1);

// якщо верхній підсписок (scanDown+1...high) має 2 або більше елементів

// виконати рекурсивний виклик 25

if (scanDown+1 < high)

Quicksort(A, scanDown+1, high);