Algorytmy sortujące – cz. I

Sortowanie jest jedną z najbardziej istotnych funkcji w różnego rodzaju systemach informatycznych – również w aplikacjach internetowych, gdzie często jest wymagany określony porządek danych wyświetlanych użytkownikowi. Mimo, że istnieje wbudowana funkcja sort() wykorzystująca algorytm quicksort warto znać inne algorytmy rozwiązujące ten problem. W cyklu artykułów przedstawię kilka najbardziej znanych i najczęściej używanych algorytmów sortowania. Na początek zaprezentuję najprostsze algorytmy o złożoności czasowej O(n2). W kolejnych częściach omówię bardziej rozbudowane algorytmy o mniejszej złożoności, aż dojdziemy do sposobów sortowania o złożoności czasowej O(n).

Sortowanie bąbelkowe

Sortowanie bąbelkowe ang. Bubble sort polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim sortuje się tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany. Jest to przykład algorytmu sortowania stabilnego.

Idea

W sortowaniu bąbelkowym przeglądamy listę porównując ze sobą kolejne pary elementów: pierwszy z drugim, drugi z trzecim, trzeci z czwartym itd. W sytuacji gdy dany element jest większy od następnego zamieniamy je pozycjami. Powyższą operację powtarzamy n razy. W każdym kolejnym cyklu przeglądamy o 1 element mniej (jest on już posortowany).

Posortujemy tablicę 4-elementową: 6 4 8 1

Implementacja

<?php
/**
 * Algorytm sortowania bąbelkowego
 *
 * @param int t - tablica z danymi - referencja
 * @param int n - rozmiar tablicy
 *
 * @return void
 */

function bubbleSort(&$t, $n) {
    for($i=0;$i<$n;$i++) { // glowna petla
        for($j=0;$j<$n-$i-1;$j++) { // przeszukiwanie w kazdym cyklu. Zawsze o 1 mniej.
            if($t[$j]>$t[$j+1]) { // jezeli element jest wiekszy od nastepnego nastepuje zamiana pozycjami
                $temp=$t[$j];
                $t[$j]=$t[$j+1];
                $t[$j+1]=$temp;
            }
        }
    }
}
?>

Złożoność obliczeniowa

Algorytm składa się z przypisywania zmiennych, instrukcji warunkowej oraz dwóch pętli.

Przypisanie do zmiennej oraz porównywanie wykonuje się w czasie stałym O(1). Pętla wewnętrzna wykona się n razy dla i=0. W każdym kolejnym obrocie będzie o 1 mniej. Jej złożoność wynosi O(n). Natomiast pętla zewnętrzna wykona się n razy – O(n). Sumując, złożoność czasowa wynosi O(n*n*1) = O(n2).

Optymalizacja

Algorytm sortowania bąbelkowego można z optymalizować dodając zmienną logiczną, w której będziemy przetrzymywać informację czy w danym obrocie pętli zaszła zamiana elementów. Dzięki temu możemy wcześniej stwierdzić czy tablica jest już całkowicie posortowana i zakończyć działanie funkcji.

<?php
/**
 * Algorytm sortowania bąbelkowego
 *
 * @param int t - tablica z danymi - referencja
 * @param int n - rozmiar tablicy
 *
 * @return void
 */

function bubbleSort(&$t, $n) {
    for($i=0;$i<$n;$i++) { // glowna petla
        $swap=false; // nie doszlo do zamiany - pozycja poczatkowa
        for($j=0;$j<$n-$i-1;$j++) { // przeszukiwanie w kazdym cyklu. Zawsze o 1 mniej.
            if($t[$j]>$t[$j+1]) { // jezeli element jest wiekszy od nastepnego nastepuje zamiana pozycjami
                $temp=$t[$j];
                $t[$j]=$t[$j+1];
                $t[$j+1]=$temp;
                $swap=true; // zamieniono elementy
            }
        }
        if(!$swap) { // jezeli nie doszlo do zamiany przerwij petle
            break;
        }
    }
}
?>

Dzięki zastosowaniu tej optymalizacji ilość obrotów głównej pętli dla podanego wcześniej przykładu zmniejszyła się z 4 do 3.

Sortowanie przez wybieranie

Sortowanie przez wybieranie ang. Selection sort polega na wyszukaniu elementu mającego znaleźć się na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy. Jest to kolejny przykład algorytmu sortowania stabilnego.

Idea

W pierwszym kroku algorytm znajduje największy element listy i zamienia go z ostatnim elementem. W następnym cyklu szuka drugiego elementu pod względem wielkości i zamienia z przedostatnim itd. W i-tym kroku szukany jest największy element spośród n-i elementów listy i zamieniany jest z elementem o n-i pozycji.

Używa się również analogicznej wariacji dla najmniejszych elementów.

Posortujemy tablicę 4-elementową: 6 4 8 1

Implementacja

<?php
/**
 * Algorytm sortowania przez wybieranie
 *
 * @param int t - tablica z danymi - referencja
 * @param int n - rozmiar tablicy
 *
 * @return void
 */

function selectionSort(&$t, $n) {
    for($i=$n-1;$i>1;$i--) { // glowna petla. Swoj "zakres" zaczyna od ostatniego elementu. Zmniejsza sie o 1 za kazdym obrotem
        $max=0; // zaznaczamy t[0] jaka najwieksza wartosc
        for($j=1;$j<$i;$j++) { // petla od 1 do i do szukania najwiekszej wartosci
            if($t[$j]>$t[$max]) { // jeezli dany element jest wiekszy od max to go oznacz jako max
                $max=$j;
            }
        }
        $temp=$t[$j]; // zamiana elementow
        $t[$j]=$t[$max];
        $t[$max]=$temp;
    }
}
?>

Złożoność obliczeniowa

Algorytm składa się z przypisywania zmiennych, instrukcji warunkowej oraz dwóch pętli.

Przypisanie do zmiennej oraz porównywanie wykonuje się w czasie stałym O(1). Pętla wewnętrzna wykona się n-1 razy dla i=n. W każdym kolejnym obrocie będzie o 1 mniej. Jej złożoność wynosi O(n). Natomiast pętla zewnętrzna wykona się n-2 razy – O(n). Sumując, złożoność czasowa wynosi O(n*n*1) = O(n2).

Sortowanie przez wstawianie

Algorytm sortowania przez wstawianie jest skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest również stabilny i nie wymaga dodatkowej pamięci.

Idea

Przed wykonaniem i-tego kroku algorytmu posortowanych jest pierwszych i-1 elementów listy. W i-tym kroku algorytmu wstawiamy i-ty element do posortowanej części listy. W tym celu przeglądamy posortowaną część listy w poszukiwaniu miejsca gdzie możemy wstawić i-ty element.

Posortujemy tablicę 4-elementową: 6 4 8 1

Implementacja

<?php
/**
 * Algorytm sortowania przez wstawianie
 *
 * @param int t - tablica z danymi - referencja
 * @param int n - rozmiar tablicy
 *
 * @return void
 */

function insertSort(&$t, $n) {
    for($i=1;$i<$n;$i++) { // glowna petla
        if($t[$i]<$t[$i-1]) { // jezeli t[i] mniejsze od t[i-1]
            $temp=$t[$i];
            for($j=$i-1;($j>=0) && ($t[$j]>$pom);$j--) { // petla szuka miejsca dla elementu temp
                $t[$j+1]=$t[$j]; // przesuwanie elementow tablicy w prawo
            }
            $j++;
            $t[$j]=$temp; // wstawienie elementu temp w wolna luke
        }
    }
}
?>

Złożoność obliczeniowa

Algorytm składa się z przypisywania zmiennych, instrukcji warunkowej oraz dwóch pętli.

Przypisanie do zmiennej oraz porównywanie wykonuje się w czasie stałym O(1). Pętla wewnętrzna wykona się n razy dla i=n. W każdym kolejnym obrocie będzie o 1 więcej. Jej złożoność wynosi O(n). Natomiast pętla zewnętrzna wykona się n-1 razy – O(n). Sumując, złożoność czasowa wynosi O(n*n*1) = O(n2).

Podsumowanie

W artykule przedstawiłem proste algorytmy sortujące, które są łatwe w implementacji, jednak nadają się one tylko do sortowania stosunkowo małych tablic, gdyż ich złożoność czasowa jest rzędu O(n2). W kolejnych częściach cyklu zaprezentuję algorytmy bardziej nadające się do sortowania dużych tablic.

Powiązane tematy

• Algorytmy sortujące – cz. II