Przegląd i testowanie metod sortowania. Część I

Któregoś dnia w komentarzach na VKontakte pokłóciłem się z jednym z pozostałych uczniów projektu. Istotą sporu było „kto wygra” – metoda sort()z klasy java.util.Arrayslub samodzielnie napisane implementacje prostych algorytmów: bańka , wstawianie , selekcja , powłoka (algorytm Shell). Dla niektórych odpowiedź na to pytanie może być oczywista, jednak skoro powstał spór, mimo że każda ze stron miała „szacowane źródła” na poparcie swojego punktu widzenia, zdecydowano się przeprowadzić badanie, rozciągające szarą materię w proces, wdrażając różne algorytmy. TL;DR: java.util.Arrays.sort() jest bezwarunkowo liderem na tablicach liczących 100 000 elementów i więcej; przy mniejszym rozmiarze metoda Shell może czasem z nią konkurować. Reszta rozważanych algorytmów jest całkowicie pusta i może być użyteczna tylko w pewnych egzotycznych warunkach. Przyjrzyjmy się teraz, jak tablice są sortowane w naszych krzemowych urządzeniach uber.

Sortowanie przez wybór. Sortowanie według wyboru

Zacznijmy od najprostszej i najbardziej oczywistej metody. Istotę tego doskonale pokazuje nam Robert Sedgwick w swoim wideo wykładzie na Courserze (przytoczę stamtąd animację, którą źle skompresowałem w gifie): View Przebiegając tablicę od pierwszego elementu, na każdym kroku mamy poszukaj minimalnego elementu po prawej stronie, z którym zamienimy bieżący. W rezultacie rezerwujemy ostateczną wersję naszej tablicy w formie posortowanej. Oto kod implementujący ten algorytm w Javie:

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;
    }

Analiza algorytmu pokazuje, że przy każdym przejściu należy przeczesać pozostałą część tablicy, czyli będziemy potrzebować dokładnie N + (N-1) + (N-2) + ... + 1 = N^ Porównania 2/2. Zatem złożoność algorytmu wynosi O(N^2). Co to znaczy? Oznacza to, że zwiększając liczbę elementów tablicy (N) 2 razy, zwiększymy czas działania algorytmu nie o 2, ale o 2^2 = 4 razy. Zwiększając N 10 razy, zwiększymy czas działania 100 razy i tak dalej. Na moim laptopie z 2012 r. z procesorem Core i3 i systemem Ubuntu 14.4 uzyskałem następujący czas sprawności:

Sortowanie przez wstawianie. Sortowanie przez wstawianie

Tutaj pomysł jest nieco inny. Wróćmy jeszcze do animacji Doktora Sedgwicka: Zobacz, co nas jeszcze czeka, nawet nie oglądaliśmy, a wszystko, co zostawiamy za sobą, zawsze pozostaje w porządku. Chodzi o to, że każdy nowy element oryginalnej tablicy „wracamy” na początek, aż „spocznie” na mniejszym elemencie. Zatem znowu mamy N przejść (dla każdego elementu oryginalnej tablicy), ale w każdym przejściu w większości przypadków nie patrzymy na całą resztę, ale tylko na część. Czyli opcję 1 + (N-1) + (N-2) + … + N = N^2/2 otrzymamy tylko wtedy, gdy każdy kolejny element będziemy musieli cofnąć na sam początek, czyli w przypadku tablicy wejściowej posortowanej „odwrotnie” (pech, pech). W przypadku już posortowanej tablicy (tutaj szczęście) pojawi się kompletny gratis - przy każdym przejściu następuje tylko jedno porównanie i pozostawienie elementu na miejscu, czyli algorytm będzie działał w czasie proporcjonalnym do N. Złożoność algorytmu zostanie określony przez najgorszy przypadek teoretyczny, czyli O(N^2). Średnio czas działania będzie proporcjonalny do N^2/4, czyli dwukrotnie szybciej niż w przypadku poprzedniego algorytmu. W mojej implementacji, ze względu na nieoptymalne użycie permutacji, czas działania był dłuższy niż w przypadku Selection. Planuję wkrótce poprawić i zaktualizować post. Oto kod i wynik jego działania na tej samej maszynie:

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;
            }
        }
    }

Sortowanie powłoki. Sortowanie powłoki

Sprytny facet, Donald Schell, zauważył już w 1959 roku, że najdroższe przypadki w algorytmie wstawiania mają miejsce, gdy element powraca bardzo daleko na początek tablicy: w pewnym przebiegu wracamy element na początek o kilka pozycji , a na innym przejście prawie przez całą tablicę do początku jest daleko i długo. Czy da się to zrobić na raz, przeskakując kilka elementów? I znalazł taki sposób. Polega na sekwencyjnym wykonywaniu specjalnych sortowań częściowych, ogólnie nazywanych sortowaniem d lub, według Sedgwicka, h-sortem (podejrzewam, że h oznacza przeskok). Na przykład 3-sort porówna dany element nie z poprzednim, ale pominie dwa i porówna z tym, który jest 3 pozycje wstecz. Jeśli zostanie zmieniony, porówna go ponownie z elementem znajdującym się 3 pozycje wstecz i tak dalej. Najważniejsze jest to, że wynikowa tablica będzie „posortowana 3”, co oznacza, że ​​nieprawidłowe położenie elementów będzie mniejsze niż 3 pozycje. Praca z tym algorytmem wstawiania będzie łatwa i przyjemna. Nawiasem mówiąc, „1-sort” to nic innego jak algorytm wstawiania =) Stosując sekwencyjnie h-sort do tablicy z malejącymi wartościami h, możemy szybciej posortować dużą tablicę. Oto jak to wygląda: Widok Wyzwaniem jest wybranie właściwej sekwencji sortowania częściowego. Od tego ostatecznie zależy wydajność algorytmu. Najbardziej powszechna jest sekwencja zaproponowana przez Donalda Knutha: h = h*3 + 1, czyli 1, 4, 13, 40, ... i tak dalej aż do 1/3 rozmiaru tablicy. Ta sekwencja zapewnia przyzwoitą wydajność i jest również łatwa do wdrożenia. Analiza algorytmu wymaga dużej ilości języka i przekracza moje możliwości. O szerokości analizy decyduje także wiele wariantów h sekwencji. Empirycznie możemy powiedzieć, że szybkość działania algorytmu jest bardzo dobra – przekonaj się sam: Milion elementów w mniej niż sekundę! A oto kod Java z sekwencją Knuta.

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;
            }
        }
    }

Sortowanie bąbelkowe. Metoda bąbelkowa

To klasyk! Prawie każdy początkujący programista implementuje ten algorytm. To taki klasyk, że doktor Sedgwick nie miał nawet do niego animacji, więc musiałem sam ją wykonać. Widok Tutaj przy każdym przejściu przemierzamy tablicę od początku do końca, zamieniając sąsiednie elementy, które są niewłaściwą kolejnością. W rezultacie największe elementy „unoszą się” (stąd nazwa) na koniec tablicy. Każdy nowy przebieg rozpoczynamy optymistycznie, mając nadzieję, że tablica jest już posortowana ( sorted = true). Jeśli na końcu przejścia zauważymy, że popełniliśmy błąd, rozpoczynamy nowe przejście. Trudność polega na tym, że ponownie przy każdym przejściu przemierzamy (prawie) całą tablicę. Porównanie następuje na każdym kroku, wymiana następuje niemal na każdym kroku, co czyni ten algorytm jednym z najwolniejszych (jeśli weźmiemy pod uwagę algorytmy realizowane racjonalnie, a nie „sortowanie potrząsające” i tym podobne). Co ciekawe, formalnie złożoność tutaj również będzie równa O(N^2), ale współczynnik będzie znacznie wyższy niż w przypadku wstawień i selekcji. Kod algorytmu:

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;
        }
    }

Czas pracy: Poczuj różnicę: ponad pół godziny na milionie elementów! Wniosek: Nigdy nie używaj tego algorytmu!!!

Podsumowanie pierwszej części

W rezultacie sugeruję przyjrzenie się ogólnej tabeli tych algorytmów. Można także porównać z wynikami metody wbudowanej java.util.Arrays.sort(). Wygląda to na jakąś magię – co może być szybszego od Shella? Napiszę o tym w kolejnej części. Tam przyjrzymy się szeroko stosowanym algorytmom szybkiego sortowania, a także sortowaniu przez scalanie, poznamy różnicę w metodach sortowania tablic od typów pierwotnych i referencyjnych, a także zapoznamy się z bardzo ważnym interfejsem w tej kwestii ; Comparable) Poniżej możesz przestudiować wykres zbudowany w skali logarytmicznej przy użyciu tabel danych. Im bardziej płaska linia, tym lepszy algorytm =) Dla tych, którzy chcą pobrać cały projekt i samodzielnie przeprowadzić testy, zachowaj link: Java Do zobaczenia w kolejnej części! =)