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.