Огляд та тестування методів сортування. Частина I

Днями у коментарях вконтакті у мене виникла суперечка з одним із інших студентів проекту. Суть суперечки полягала в тому, «хто кого» — метод 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 До зустрічі в наступній частині! =)