5
2.1. Сортування вибором (Selection sort)
Метод сортування вибором заснований на двох основних правилах.
1.Вибирається елемент з найменшим ключем.
2.Міняється місцями з першим елементом.
Ці операції повторюються з залишившимися n-1 елементами, потім n-2 елементами до тих пір поки не залишиться один елемент — найбільший.
function selectionSort(T[n] a): for i = 0 to n - 2
for j = i + 1 to n - 1 if a[i] > a[j]
swap(a[i], a[j])
(Псевдокод)
Аналіз сортування вибором
Щоб проаналізувати хід роботи сортування методом вибору треба звернути увагу, що, якщо у нас n елементів, зовнішній цикл виконується n - 1 раз, тому у нас n - 1 замін. У кожній ітерації зовнішнього циклу ми порівнюємо всі елементи від i + 1 до кінця масиву A. В перший прохід ми порівнюємо всі елементи від A [1] до A [n - 1], тому у нас n - 1 порівнянь. У другій прохід ми порівнюємо всі елементи від A [2] до A [n - 1], тому у нас n - 2 порівнянь. В останньому проході циклу ми порівнюємо останні два елементи, A [n - 2] і A [n - 1], і у нас всього одне порівняння. Виходить, що всього порівнянь у нас
1+2+...+(n−1)=1+2+...+(n−1)+n−n= n(n+1)−n=n (n−1)
2 2
Виходячи з цього можна сказати що складність сортування сетодом вибору дорівнює O(n−1)=O(n) замінам та O(n(n−1)/2)=O(n2) порівнянням. Зазвичай порівняння виконуються швидше, ніж заміни, так як операція заміни включає в себе переміщення даних. Чим більше переставлятимемо дані, тим очевидніше стає різниця.
6
Реалізація
for(i=0;i<n-1;i++)
{
min=arr[i]; loc=i;
for(j=i+1;j<n;j++)
{
if(min>arr[j])
{
min=arr[j]; loc=j;
}
}
temp=arr[i]; arr[i]=arr[loc]; arr[loc]=temp;
}
7
2.2 Сортування вставкою (Insertion sort)
Суть алгоритму сортування вставками полягає в тому що
1.На першому кроці порівнюються другий та перший елемент
2.Якщо порядок між ними, в залежності від типу сортування (за зростанням чи за спаданням) порушений, то перший елемент пересувається на одну позицію вправо. Тепер відсортований масив складається з двох елементів.
Продовжуючи ітераційний процес далі, беремо наступний (третій, четвертий і так далі) елемент і по черзі порівнюємо його, починаючи з кінця, з іншими елементами в уже відсортованому масиві.
Виходячи з методу роботи алгоритма можна сказати що сортування вставкою буде найкращим чином показувати себе на частково відсортованих даних.
function insertionSort(a): for i = 1 to n - 1
j = i - 1
while j 0 and a[j] > a[j + 1] swap(a[j], a[j + 1])
j--
(Псевдокод)
Аналіз сортування вставкою
Для оцінки складності алгоритму треба розуміти стан вихідного масиву. Якщо масив вже упорядкований, то всі елементи залишаться на своєму місці і вкладений цикл не буде виконаний жодного разу. У цьому випадку складність алгоритму сортування вставками - лінійна, тобто O(n) Аналогічно, якщо масив «майже впорядкований», тобто для перетворення його в упорядкований потрібно поміняти місцями декілька сусідніх або близьких елементів, то складність також буде лінійною. Але якщо масив упорядкований у зворотному порядку, наприклад, кожен елемент більше поперелньго, а необхідно досягти зворотного порядку, то кожен елемент буде пересуватися максимально вліво, тобто до самої крайньої позиції. У цьому випадку кількість виконуваних переміщень дорівнюватиме:
1+2+...+(n−1)+n= n(n+1)=O(n2)
2
Укращому випадку час роботи - лінійний, в гіршому випадку — квадратичний.
Увипадку якщо в середньому елементи масиву впорядковано випадково. Математичне сподівання кількості переміщень елементів дорівнюватиме половині від числа переміщень в гіршому випадку, тобто математичне очікування числа переміщень дорівнюватиме:
n(n+1)=O(n2 )
4
8
Реалізація
for (i = 1; i < N; i++)
{
key = arr[i]; j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j]; j = j - 1;
}
arr[j + 1] = key;
}
9
2.3 Шейкерне сортування (Shaker sort)
Принцип работи полягає в багаторазовій пробіжці по масиву сусідні елементи порівнюються і, в разі необхідності, міняються місцями. При досягненні кінця масиву напрямок змінюється на протилежний. Таким чином по черзі виштовхуються великі і дрібні елементи масиву в кінець і початок структури відповідно.
function ShakerSort( A : list of sortable items ) defined as: do
swapped := false
for each i in 0 to length( A ) - 2 do: if A[ i ] > A[ i + 1 ] then
order
swap( A[ i ], A[ i + 1 ] ) swapped := true
end if end for
if not swapped then break do-while loop
end if
swapped := false
for each i in length( A ) - 2 to 0 do: if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] ) swapped := true
end if end for
while swapped end procedure
|
|
(Псевдокод) |
Аналіз шейкерного сортування |
||
Найменша кількість порівнянь |
Cmin=n−1 . Кнут знайшов, що середня кількість |
|
проходів пропорційна n−k1 √ |
|
та середня кількість порівнянь пропорційна |
n |
||
1 |
[n2−n(k2 +ln(n))] |
. Тому складність шейкерного сортування |
O(n2 ) в гіршому та |
2 |
|
|
|
середньому випадках та O(n) в кращому . Таким чином шейкерне сортування має сенс використовувати коли ми знаємо що масив даних вже майже відсортовано. Що досить рідко зустрічається на практиці.
Реалізація