Opisać popularne metody sortowania, podać przykłady algorytmów
ALGORYTMY SORTUJĄCE
Algorytmy sortowania są jednymi z najbardziej znanych algorytmów. Ponieważ proces sortowania jest bardzo ważny w dzisiejszym oprogramowaniu tak więc powstało wiele algorytmów, które lepiej lub gorzej rozwiązują ten problem. Sortować można nie tylko tablice, ale także inne struktury danych, chociażby na przykład listy.
Cechą charakteryzującą niektóre algorytmy sortowania jest to, że działają one w miejscu. Znaczy to, że w czasie procesu sortowania tylko stała liczba elementów tablicy wejściowej jest przechowywana poza nią. Tak więc algorytmy, które nie działają w miejscu wymagają dodatkowej pamięci.
Najważniejszym chyba parametrem, który określa algorytmy sortowania jest ich złożoność. Można udowodnić, że dolna granica złożoności algorytmów, które porównują elementy tablicy wejściowej wynosi n*lg n. Granica ta może być przekroczona przez algorytmy, które nie wykonują porównań. Takimi są na przykład: sortowanie poprzez zliczanie, pozycyjne, kubełkowe. Najbardziej uniwersalnym i w większości przypadków najszybszym jest algorytm QuickSort. Inną jego zaletą jest jego prostota i zwięzłość.
Sortowanie kubełkowe, sortowanie koszykowe
(angielskie bucket sort),
Jest to sortowanie, w którym przedział sortowanych liczb (o rozkładzie jednostajnym, co jest założeniem) dzieli się na n podprzedziałów jednakowej długości (kubełki), sortuje zawartość kubełków, a następnie przegląda się po kolei kubełki i wypisuje uporządkowany ciąg liczb.
Sortowanie kubełkowe (bucket sort) to algorytm, działający w czasie liniowym (O(n)). Liczby przeznaczone do tego sortowania powinny być liczbami z przedziału [0;1) i powinny być dosyć równo rozłożone w tymże przedziale. Cały algorytm opiera się na podziale przedziału [0;1) na pewną ilość równych podprzedziałów, tzw. kubełków. Następnie każda z liczb przeznaczona do sortowania jest "wrzucana" do odpowiedniego kubełka. Aby otrzymać posortowane liczby najpierw sortuje się liczby w każdym z kubełków, a następnie łączy się je wszystkie po kolei.Do reprezentacji kubełków najlepiej jest użyć struktur danych zwanych listami. Jako algorytmu do sortowania kubełków można użyć sortowania przez wstawianie. Mimo, że ma on złożoność O(n2) to ogólnie sortowanie kubełkowe ma złożoność O(n). Wynika to z tego, że dane wejściowe są równomiernie rozłożone w przedziale [0;1).W przypadku, gdy mamy do posortowania liczby spoza przedziału [0;1) to należy każdą z nich podzielić przez sumę największej liczby w danych ciągu i liczby 1. W ten sposób wszystkie liczby będą w zadanym przedziale. Należy dodać w tym przypadku 1 do największej liczby, bo gdy będziemy dzielić właśnie ją to otrzymamy liczbę 1, a ta liczba do przedziału podanego wyżej nie należy.
Sortowanie bąbelkowe
(angielskie bubble sort),
Jest to sortowanie polegające na przeglądaniu po kolei elementów porządkowanego ciągu i zamienianiu miejscami sąsiadujących elementów tak, aby spełniały relację porządkującą; w ten sposób elementy mniejsze (“lżejsze”) przesuwają się na początek ciągu.Dla n elementów ciągu złożoność sortowania bąbelkowego wynosi O(n2). Sortowanie bąbelkowe jest sortowaniem stabilnym.
Bardzo często, pisząc program, mamy do czynienia z problemem nieposortowanych liczb. Mamy tablicę pełną liczb, ułożonych w różnej (np. losowej) kolejności i chcemy posortować ją, tak, że najmniejsze elementy będą na początku, największe zaś - na końcu tablicy. Możemy to zastosować najprostszy chyba sposób sortowania - sortowanie bąbelkowe. Nazwa wzięła się stąd, że algorytm przesuwa "cięższe" (czyli większe) "bąbelki" (liczby) na koniec. Tak jakby spadały.
Napisanie programu sortującego dziesięcioelementową tablicę jest bardzo proste. Potrzebne są (oprócz tablicy) trzy dodatkowe zmienne: dwie liczbowe (licznik dla pętli i tymczasowe przechowywanie liczby) i jedna logiczna (boolean - jeśli algorytm "zauważy", że dwie stojące obok siebie liczby są w złej kolejności ustawia wartość "false" dla tej zmiennej). Na początku trzeba napisać pętlę repeat, którą ma zostać zakończona, kiedy zmienna logiczna (nazwijmy ją posort) przyjmie wartość true. Następnie, po kolei, od pierwszego do przedostatniego elementu "przechodzimy" tablicę. Jeśli napotkamy sytuację, w której następna (względem aktualnie ustalonej) liczba jest mniejsza od aktualnej, ustawiamy posort na false (tablica nie jest jeszcze posortowana) i zamieniamy te dwie liczby miejscami. Przed całą pętlą "przechodzenia" tablicy, na samym początku pętli głównej ustawiamy (koniecznie!) posort na true i dopiero kiedy okaże się, że tablica jest nieposortowana, zmienna ta zostanie ustawiona na false. Jeśli tablica będzie posortowana, wartość zmiennej pozostanie true i pętla się zakończy.
Sortowanie bąbelkowe z kresem górnym
Może się zdarzyć sytuacja, gdy tablica będzie już uporządkowana, zanim zrobimy n-1 przebiegów lub po k przebiegach więcej niż k liczb od końca będzie na swoim miejscu. Ten problem także da się ominąć. Wystarczy do naszego programu wprowadzić zmienną, która będzie reprezentować w której pozycji nastąpiła ostatnia zamiana elementów tablicy. Ta zmienna to jakby kres następnego przebiegu. Ten wariant sortowania nazywa się sortowaniem bąbelkowym z kresem górnym.
Sortowanie przez wybór
(angielskie selectsort)
Jest to sortowanie, w którym w każdym kroku algorytmu znajduje się najmniejszy element w sortowanym ciągu, po czym przenosi się ten element na kolejną pozycję do ciągu wynikowego (przez zamianę elementów miejscami).
Sortowanie przez wstawianie
(insertion sort)
Sortowanie przez wstawienie to algorytm, którego czas działania wynosi O(n2). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci (działa w miejscu). Często stosujemy go podczas gry w karty, biorąc je ze stołu. Biorąc po jednej karcie ze stołu wstawiamy ją w odpowiednie miejsce do kart, które mamy w ręce.
Sortowanie przez zliczanie
(counting sort)
Sortowanie przez zliczanie jest jednym z najszybszych algorytmów sortowania danych, a przy tym bardzo prostym do wytłumaczenia. Algorytm ten działa w czasie O(n), tak więc jest to sortowanie w czasie liniowym. Mimo swoich zalet, sortowanie przez zliczanie ma swoje dwie poważne wady. Po pierwsze - do tego sortowania potrzebna jest dodatkowa pamięć(czyli nie jest to sortowanie w miejscu), a po drugie - tym sposobem można sortować tylko liczby całkowite z określonego przedziału. Niewiadomo dlaczego, ale algorytm ten mimo swojej prostoty nie jest powszechnie znany, a tym bardziej używany.
Sortowanie pozycyjne
(radix sort)
Stosowane jest do sortowania elementów, które składają się z szeregu pozycji (mogą to być liczby, gdzie pozycjami są poszczególne cyfry; wyrazy - w tym przypadku są to poszczególne litery; mogą to także być inne dane, np. daty). Algorytm ten wymaga użycia innego algorytmu sortowania podczas swego działania, co ważne sortowanie to musi być stabilne. Gdy jako dodatkowego algorytmu sortowania użyjemy sortowania przez zliczanie to algorytm sortowania pozycyjnego działa w czasie O(n). Sortowanie pozycyjne stosuje się nie tylko do sortowania liczb, czy wyrazów. W ten sposób możemy także sortować np. daty. Musimy jednak pamiętać, aby sortować od pozycji najmniej znaczących. W przypadku dat - najpierw sortujemy je według dni, potem według miesięcy, a na końcu według lat. Sortowanie pozycyjne możemy także zastosować do sortowania rekordów baz danych. Na przykład chcemy posortować książkę telefoniczną według nazwisk, a w razie gdyby się one powtarzały to według imion, a w przypadku identyczności imion i nazwisk według numeru telefonu. Aby otrzymać taki wynik powinniśmy tą książkę telefoniczną posortować najpierw według numeru telefonu, potem według imion, a na końcu według nazwisk. Złożoność obliczeniowa takiego sortowania pozycyjnego na pewno nie będzie O(n). Wynika to z tego, że do posortowania np. nazwisk trudno jest użyć sortowania przez zliczanie.
Sortowanie wyrazów
Z sortowaniem wyrazów jest podobnie jak z sortowaniem liczb. W tym przypadku pozycjami są poszczególne litery danego wyrazu. Jednakże jest pewna różnica jeśli chodzi o sortowanie wyrazów różnej długości. W tym przypadku odpowiednią ilość znaków dopisujemy za wyrazem, a nie jak to było w przypadku liczb - przed. Znak ten musi być traktowany jako wyżej w alfabecie, niż wszystkie inne - może to być na przykład spacja.
Sortowanie QuickSort
Jest to jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie - proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n2), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych.
Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.
Inna odmiana QuickSort
Wyżej wspomniane jest, że algorytm szybkiego sortowania ma pesymistyczny czas działania O(n2). Występuje to w przypadku, gdy tablica wejściowa jest posortowana odwrotnie, tzn. jej wyrazy stanowią ciąg nierosnący.