10
bool swapped = true; int start = 0;
int end = n - 1;
while (swapped)
{
swapped = false;
for (int i = start; i < end; ++i)
{
if (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true;
}
}
if (!swapped) break;
swapped = false; --end;
for (int i = end - 1; i >= start; --i)
{
if (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true;
}
}
++start;
}
11
2.4 Сортування підрахунком (Counting sort)
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.. Нехай, наприклад, є масив A із чисел, по модулю менших 100. Тоді можна створити допоміжний масив B:array[-100..100] of integer для обчислення кількості елементів і у масиві А, «пробігти» весь вихідний масив і обчислювати частоту повторюваності кожного елемента — тобто якщо A[i]=х, то B[х] слід збільшити на одиницю. Потім «пробігти» лічильником i масив B, записуючи в новий масив A число i B[i] разів.
Аналіз сортування підрахунком
В алгоритмі присутні тільки прості цикли довжини N (довжина масиву), та один цикл довжини K (величина діапазону). Отже, обчислювальна складність роботи алгоритму становить В алгоритмі використовується додатковий масив. Тому алгоритм потребує
додаткової пам’яті.
В подібній реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (наприклад, сортування за розрядами). Використання даного алгоритму є доцільним тільки у випадку малих K.
Реалізація
int arr1[10];
int count_arr[10]; int x = arr[0];
for (int i = 1; i < n; i++) { if (arr[i] > x)
x = arr[i];
}
for (int i = 0; i <= x; ++i) { count_arr[i] = 0;
}
for (int i = 0; i < n; i++) { count_arr[arr[i]]++;
}
for (int i = 1; i <= x; i++) {
12
count_arr[i] += count_arr[i - 1];
}
for (int i = n - 1; i >= 0; i--) { arr1[count_arr[arr[i]] - 1] = arr[i]; count_arr[arr[i]]--;
}
for (int i = 0; i < n; i++) { arr[i] = arr1[i];
}
2.5 Швидке сортування (Quick sort)
Швидке сортування хоча і було розроблене досить давно, є найбільш широко застосовуваним і одним з найбільш ефективних алгоритмів.
Прнцип роботи алгоритму полягає в тому що :
1.Вибирається опорний елемент (наприклад, посередині масиву).
2.Масив проглядається зліва-направо і проводиться пошук найближчого елемента, більшого ніж опорний.
3.Масив проглядається справа-наліво і проводиться пошук найближчого елемента, меньшого ніж опорний.
4.Знайдені елементи міняються місцями.
5.Триває одночасний двосторонній перегляд по масиву з подальшими обмінами відповідно до пунктів 2-4.
6.В кінці кінців, перегляди зліва-напрво і справа-наліво сходяться в одній точці, яка ділить масив на два підмасива.
7.До кожного з двох підмасива рекурсивно застосовується "Швидке сортування".
Аналіз швидкого сортування
Для того щоб проаналізувати властивості швидкого сортування мі повинні досконало зрозуміти процес розбиття масиву. Після вибору границі , розбиттю підлягає вест масив. Таким чином виконуєть n порівнянь . Кількість обмінів можна оцінити за допомогою наступного міркування.
Припустимо, що масив даних що потрібно розділити складається з n ключів 1, ..., n, і ми обрали x як границю. Після поділу х буде займати в масиві позицію х. Число потрібних обмінів дорівнює числу елементів в лівій частині х-1, помноженому на вірогідність того, що ключ потрібно обміняти. Ключ обмінюється, якщо він не менише ніж х. Така ймовірність дорівнює (n−x+1)/n . Очікуване число обмінів обчислюється за допомогою підсумовування всіх можливих варіантів вибору
|
1 |
n |
x−1 |
|
n |
|
1 |
кордону і ділення цієї суми на n : |
M= n |
∑x=1 |
|
(n−x +1)= |
6 |
− |
|
n |
6 n |
12
Отже, очікуване число обмінів дорівнює приблизно n / 6.
Якщо припустити, що нам дуже щастить і ми завжди вибираємо в якості кордону медіану, то кожне поділ розбиває масив на дві рівні частини і число проходів, необхідних для сортування, дорівнює log(n) . Тоді загальне число порівнянь складе n log (n) , а загальне число обмінів n/6 log(n) .
Реалізація
static void swap(int* a, int* b)
{
int t = *a; *a = *b; *b = t;
}
static int partition (int arr[], int low, int high, bool direct)
{
int pivot = arr[high]; int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if(direct)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
else
if (arr[j] >= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); return (i + 1);
}
static void quickSort(int arr[], int low, int high, bool direct)
{
if (low < high)
{
int pivot = partition(arr, low, high, direct); quickSort(arr, low, pivot - 1, direct);
14
quickSort(arr, pivot + 1, high, direct);
}
}
2.6 Сортування злиттям (Merge sort)
Алгоритм сортування злиттям заснований на ідеї, що два відсортованих масиви можна злити в один за час, що дорівнює сумарній довжині цих масивів.
Для цього порівняємо перші елементи даних масивів. Той елемент, який менше, скопіюємо в кінець результуючого масиву (який спочатку порожній) і в цьому масиві перейдемо до наступного елементу. Будемо повторювати цей процес (вибираємо з початку двох масивів найменший елемент, копіюємо його в результуючий масив), поки один з вихідних масивів не скінчиться. Після цього залишившиєся елементи (один з двох вихідних масивів буде непорожній) скопіюємо в результуючий масив.
Для того, щоб не видаляти початкові елементи з масивів, заведемо два індексу i і j, що вказують на поточні елементи в кожному масиві. Замість видалення елементів будемо пересувати ці індекси. В кінці додамо до результуючому масиву залишилися елементи з двох вихідних масивів A [i:] + B [j:]
Аналіз сортування злиттям
Оцінимо складність цього алгоритму. Нехай масив містить n елементів. Тоді за його можна розділити на дві частини і після сортування злити їх разом.
Кожна з цих двох частин має розмір n/2, і за кроків кожну з них можна поділити на дві частини розміром n/4 і потім після сортування злити їх разом. Аналогічно, чотири частини розміром n/4 за сумарне кроків діляться на частини розміром n/8 і зливаються разом. Цей процес «в глибину» триває стільки раз, скільки разів можна число n ділити на 2, до тих пір, поки розмір частини не стане дорівнює 1, тобто log2 (n) . Разом, загальна складність цього алгоритму
дорівнює O(n log2 n) .
Одним з недоліків сортування злиттям є той факт, що він вимагає багато допоміжної пам'яті (стільки ж, який розмір вихідного масиву) для реалізації.