20. Różne algorytmy sortowania.
Bez względu na konkretne algorytmy, sortowanie można sklasyfikować niezależnie na pewne kategorie:
● adaptacyjne (zmienia swoje działanie w zależności od układu elementów sortowanego zbioru) i nieadaptacyjne (działa tak samo niezależnie od układu elementów sortowanego zbioru),
● wewnętrzne (ma dostęp do całego sortowanego zbioru) i zewnętrzne (ma dostęp do sortowanego zbioru blokami),
● bezpośrednie (stosowane przy małych elementach; operacja wstawiania odbywa się na elementach) i pośrednie (stosowne przy dużych elementach; operacja wstawiania odbywa się na wskaźnikach do elementów),
● stabilne i niestabilne - dotyczą sortowania elementów o dwóch kluczach. Sortowanie stabilne, to takie, które sortuje wg drugiego klucza elementy posortowane wcześniej wg pierwszego klucza, zachowując względną kolejność względem pierwszego klucza. To znaczy, że jeśli dwa elementy mają ten sam drugi klucz, to przy ponownym sortowaniu nie zostanie zmieniona ich kolejność, jaką nadano podczas pierwszego sortowania.
Sortowanie bąbelkowe - sprawdzamy całą tablicę od końca, jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami i znów zaczynamy przeszukiwać tę tablicę od końca. Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów. Realizuje się to najczęściej za pomocą zmiennej logicznej. Algorytm nosi nazwę bąbelkowego, gdyż najmniejsze liczby "wypływają" z dołu tablicy na jej szczyt.
Jest nieadaptacyjne, wewnętrzne i stabilne oraz nie wymaga dodatkowej pamięci.
Sortowanie przez wstawianie - pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza.
Jest adaptacyjne, wewnętrzne i stabilne oraz nie wymaga dodatkowej pamięci.
Sortowanie przez wybór (selekcję) - metoda ta nazywana jest sortowaniem przez wymianę gdyż na początku szukany jest najmniejszy element, po znalezieniu go jest on zamieniany z pierwszym elementem tablicy. Następnie szukany jest znów najmniejszy element, ale począwszy od elementu drugiego (pierwszy - najmniejszy jest już wstawiony na odpowiednie miejsce), po jego znalezieniu jest on zamieniany z drugim elementem. Czynność tą powtarzamy kolejno na elementach od trzeciego, czwartego, aż do n-tego.
Jest nieadaptacyjne, wewnętrzne i stabilne oraz nie wymaga dodatkowej pamięci.
Sortowanie szybkie - algorytm działa rekursywnie - wybierany jest pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga sortowania.
Jest zewnętrzne i niestabilne.
Jeśli przez l oznacza się indeks pierwszego, a przez r - ostatniego elementu sortowanego fragmentu tablicy, zaś przez i - indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym, pascalo-podobnym zapisem:
PROCEDURE Quicksort(l, r)
BEGIN
IF l < r THEN { jeśli fragment dłuższy niż 1 element }
BEGIN
i = PodzielTablice(l, r); { podziel i zapamiętaj punkt podziału }
Quicksort(l, i-1); { posortuj lewą część }
Quicksort(i, r); { posortuj prawą część }
END
END