Днями у коментарях вконтакті у мене виникла суперечка з одним із інших студентів проекту. Суть суперечки полягала в тому, «хто кого» — метод
sort()
із класу java.util.Arrays
або самописні реалізації простих алгоритмів: bubble (бульбашкова), insertion (вставками), selection (вибором), shell (алгоритм Шелла). Для деяких відповідь на це питання може бути очевидною, але якщо суперечка виникла, при тому, що у кожної зі сторін були «шановні джерела» на користь своєї точки зору, було прийнято рішення провести дослідження, порозімнявши в процесі сіру речовину, реалізуючи різні алгоритми. TL; DR: java.util.Arrays.sort()
беззастережно лідирує на масивах від 100 000 елементів, при меншому розмірі з ним може потягатися метод Шелла. Інші розглянуті алгоритми зливають начисто і можуть бути корисні лише за якихось екзотичних умов. Тепер давайте розглянемо, як здійснюється сортування масивів в наших убер-девайсах з кремнію.
Selection sort. Сортування вибором
Почнемо з найпростішого та очевидного способу. Суть його нам чудово демонструє Роберт Седжвік у своїй відеолекції на coursera (наводжу погано перетиснуту в gif мною анімацію звідти): Подивитися Пробігаючи по масиву з першого елемента, ми на кожному кроці шукаємо у правій частині мінімальний елемент, з яким і міняємо місцями поточний. В результаті ми залишаємо за собою остаточний варіант нашого масиву у відсортованому вигляді. Ось код, що реалізує цей алгоритм на Java:public void sort(int[] array) {
int n = array.length;
for (int i = 0; i < n; i ++) {
int minIndex = min(array, i, n - 1);
swap(array, i, minIndex);
}
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static int min(int[] array, int begin, int end) {
int minVal = array[begin];
int minIndex = begin;
for (int i = begin + 1; i <= end; i++) {
if (array[i] < minVal) {
minVal = array[i];
minIndex = i;
}
}
return minIndex;
}
Аналіз алгоритму показує, що необхідно на кожному проході прошерстить звістку залишок масиву, тобто нам знадобиться рівно N + (N-1) + (N-2) + … + 1 = N ^ 2/2 порівнянь. Отже, складність алгоритму становить O(N^2). Що це означає? А означає це, що, збільшивши кількість елементів у масиві (N) у 2 рази, ми збільшимо час роботи алгоритму не в 2, а в 22 = 4 рази. Збільшивши N у 10 разів, час роботи збільшимо у 100 разів і так далі. На моєму ноутбуці 2012 з процесором Core i3 під Ubuntu 14.4 я отримав наступний час роботи:
Insertion sort. Сортування вставками
Тут ідея дещо інша. Знову ж таки, звернемося до анімації від Доктора Седжвіка: Подивитися Те, що попереду, нами ще навіть не переглянуто, а все, що залишаємо позаду себе, завжди залишається збудованим по порядку. Суть у тому, що кожен новий елемент вихідного масиву ми «повертаємо» до початку, доки він не «упреться» у менший елемент. Таким чином, у нас знову N проходів (для кожного елемента вихідного масиву), але в кожному проході здебільшого ми переглядаємо не весь залишок, а лише частину. Тобто варіант 1 + (N-1) + (N-2) + … + N = N^2/2 ми отримаємо тільки якщо кожен наступний елемент нам доведеться повертати до самого початку, тобто у випадку відсортованого «навпаки» вхідного масиву (не щастить, так нещастить). У разі вже відсортованого масиву (ось везуха ваще) буде повна халява – на кожному проході лише одне порівняння та залишення елемента на місці, тобто відпрацює алгоритм за час, пропорційне N. Складність алгоритму буде визначатися гіршим теоретичним випадком, тобто O(N^2). Середньо ж, час роботи буде пропорційно N^2/4, тобто, вдвічі швидше попереднього алгоритму. У моїй реалізації через неоптимальне використання перестановки час роботи вийшов більшим, ніж у Selection. Планую найближчим часом виправити та оновити пост. Ось код та результат його роботи на тій же машині:public void sort(int[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = i; j >= 1; j--) {
if (array[j] < array[j - 1])
swap(array, j, j - 1);
else
break;
}
}
}
Shell sort. Сортування Шелла
Розумний мужик Дональд Шелл аж у 1959-му році зауважив, що в алгоритмі вставками найдорожче обходяться випадки, коли елемент повертається дуже далеко до початку масиву: на якомусь проході ми повернемо елемент до початку на пару позицій, а на іншому проході майже через весь масив на початок – далеко й довго. Чи не можна це зробити одразу, стрибаючи через кілька елементів? І такий спосіб знайшов. Полягає він у послідовному виконанні спеціальних часткових сортувань, званих у загальному вигляді d-sort або, у Седжвіка, h-sort (підозрюю, h означає hop – стрибок). 3-sort, наприклад, порівнюватиме аналізований елемент не з попереднім, а пропустить два і порівняє з віддаленим на 3 позиції назад. Якщо змінабо, він його порівняє знову з елементом на 3 позиції тому й таке інше. Суть у тому, що отриманий у результаті масив буде «3-відсортований», тобто неправильність становища елементів становитиме менше 3х позицій. Працювати з таким алгоритмом вставки буде легко та приємно. До речі, «1-sort» є нічим іншим, як просто алгоритмом вставки =) Послідовно застосовуючи до масиву h-sort зі зменшенням значення h, ми зможемо відсортувати великий масив швидше. Ось як це виглядає: Складність тут полягає в тому, як вибрати правильну послідовність часткових сортувань. Від цього, у результаті залежить продуктивність алгоритму. Найбільш поширеною є послідовність, запропонована Дональдом Батігом: h = h*3 + 1, тобто 1, 4, 13, 40, … і так до 1/3 розміру масиву. Така послідовність забезпечує гідну продуктивність, і навіть проста у реалізації. Аналіз алгоритму вимагає тонн матану і мною не заможний. Обширність аналізу як і визначається безліччю варіантів послідовностей h. Емпірично можна сказати, що швидкість алгоритму дуже хороша – дивіться самі: Мільйон елементів менше, ніж за секунду! А ось код на Java з батоговою послідовністю.public void sort(int[] array) {
int h = 1;
while (h*3 < array.length)
h = h * 3 + 1;
while(h >= 1) {
hSort(array, h);
h = h/3;
}
}
private void hSort(int[] array, int h) {
int length = array.length;
for (int i = h; i < length; i++) {
for (int j = i; j >= h; j = j - h) {
if (array[j] < array[j - h])
swap(array, j, j - h);
else
break;
}
}
}
Bubble sort. Метод бульбашки
Це класика! Цей алгоритм реалізує майже кожен програміст-початківець. Це настільки класика, що в Доктора Седжвіка навіть не знайшлося анімації для нього, тому мені довелося попрацювати самому. Тут на кожному проході ми обходимо масив з початку до кінця, змінюючи місцями сусідні елементи, що стоять не по порядку. В результаті найбільші елементи «спливають» (звідси і назва) наприкінці масиву. Кожен новий прохід ми починаємо, оптимістично сподіваючись, що масив уже відсортований (sorted = true
). Наприкінці проходу, якщо бачимо, що помаболися, починаємо новий прохід. Складність тут полягає в тому, що ми знову ж таки обходимо весь (майже) масив на кожному проході. Порівняння відбувається на кожному кроці, обмін - майже на кожному, що робить даний алгоритм одним з найповільніших (якщо розглядати раціонально реалізовані, а не "сортування струшуванням" та інші). Цікаво, що формально складність і тут дорівнюватиме O(N^2), тільки коефіцієнт набагато вищий, ніж у вставок і виборів. Код алгоритму:
public void sort(int[] array) {
boolean isSorted;
int nMinusOne = array.length - 1;
for(int i = 0; i < nMinusOne; i++) {
isSorted = true;
for (int j = 0; j < nMinusOne - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
isSorted = false;
}
}
if (isSorted)
return;
}
}
Час роботи: Відчуйте різницю: більше півгодини на мільйон елементів! Висновок: Ніколи не використовуйте цей алгоритм!
Резюме першої частини
Як підсумок пропоную подивитися загальну таблицю цих алгоритмів. Можете також порівняти з результатами для вбудованого методуjava.util.Arrays.sort()
. Схоже на якусь магію — що ж може бути швидшим за Шелла? Про це напишу у наступній частині. Там ми розглянемо широко застосовувані алгоритми швидкого сортування, а також сортування злиттям, дізнаємося про різницю в методах сортування масивів з примітивів і типів посилань, а також познайомимося з дуже важливим у цій справі інтерфейсом. Нижче можете вивчити графік, побудований в логарифмічному масштабі за Comparable
даними таблиці. Чим більш порожня йде лінія, тим краще алгоритм =) Хто хоче скачати весь проект і прогнати тести у себе, тримайте посилання: Java До зустрічі в наступній частині! =)
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ