Алгоритми «швидкого» сортування

Базується на принципі «розділяй і пануй» і операції вибірки. Залежно від способу поділу набору даних на частини, виділяють декілька видів швидкого сортування:

1. Базовий алгоритм.

Суть полягає у поділі набору на дві частини, котрі сортуються незалежно одна від одної. Розташування точки поділу залежить від вихідного порядку елементів у наборі. Елемент, що поділяє набір, визначається випадково (часто - крайній правий елемент), потім (після першого «перегляду» набору даних) розміщується у свою кінцеву позицію і виконується перегрупування набору даних наступним чином: елементи з меншим значенням поміщаються зліва, з більшим – справа. Потім кожна частина сортується окремо.

public static int next(char m[], int k, int r) {

int i = k,

j = r;

char ch = m[r], t;

while(true) {

while (m[i] < ch) i++;

while (m[--j] > ch)

if (j == k) break;

if (i >= j) break;

t = m[i]; m[i] = m[j]; m[j] = t;

}

t = m[i]; m[i] = m[r]; m[r] = t;

return i;

}

public static void sort(char m[], int k, int r) {

if (r <= k) return;

int i = next(m, k, r);

sort(m, k, i-1);

sort(m, i+1, r);

}

2. З поділом на три частини.

Суть полягає у поділі набору даних на три частини: елементи із значенням рівним елементу-роздільнику, що зустрічаються у лівій частині, переміщуються до лівого краю, а елементи з цим же значенням, але з правої частини, переміщуються до правого краю, потім частини сортуються окремо. (Тобто, після першого «перегляду» набору даних, зліва – менші елементи, справа – більші, а посередині – розподільник і рівні йому елементи)

public static void sort(char m[], int k, int r) {

if (r <= k) return;

char ch = m[r], temp;

int i = k, j = r, p = k, q = r;

while(true) {

while (m[i] < ch) i++;

while (m[--j] > ch)

if (j == k) break;

if (i >= j) break;

temp = m[i]; m[i] = m[j]; m[j] = temp;

if (m[i] == ch) {

temp = m[p]; m[p] = m[i]; m[i] = temp; p++;

}

if (m[j] == ch) {

q--; temp = m[q]; m[q] = m[j]; m[j] = temp;

}

}

temp = m[i]; m[i] = m[r]; m[r] = temp;

j = i-1; i = i+1;

for (int n=k; n<p; n++, j--) {

temp = m[n]; m[n] = m[j]; m[j] = temp;

}

for (int n=r-1; n>=q; n--, i++) {

temp = m[n]; m[n] = m[i]; m[i] = temp;

}

sort(m, k, j);

sort(m, i, r);

}

3. З розрахунком медіани з трьох елементів.

Суть – розподільник обирається випадково з трьох (в основному з першого, останнього і середнього);

3.1. Середній міняється місцями з передостаннім;

3.2. Перший, передостанній і останній елементи впорядковуються (найменший – на перше місце, найбільший – на останнє);

3.3. Сортується набір даних між першим і передостаннім елементами (знову беруться перший і останній у цьому наборі, порівнюються їх значення;);

3.4. Завершенням рекурсивного сортування є перевірка умови: якщо кількість елементів у під-наборі менше деякого встановленого значення, то сортування у такій частині даним алгоритмом ігнорується.

Поиск по сайту: