Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ten wykład poświęcimy prostym algorytmom sortowania. Zanalizujemy ich wady i zalety, co przygotuje nas do poszukiwania algorytmów lepszych. Zacznijmy od zdefiniowania problemu.

Definicja problemu

Niech będzie zbiorem liniowo uporządkowanym z relacją porządkującą i niech będzie ciągiem elementów z , dla pewnego całkowitego . Należy znaleźć permutację taką, że .

Uwaga: dla pary elementów będziemy pisali (), gdy () oraz .


W tym wykładzie przyjmujemy, że elementy ciągu znajdują się w tablicy , tzn. . Będziemy także chcieli, żeby posortowany ciąg znajdował się nadal w tablicy , tzn. wynikiem sortowania ma być . Dla wygody dalszych rozważań przyjmijmy, że tablica jest indeksowana od , i że zawiera element, który nie jest większy od żadnego elementu z , tzn. dla każdego , .


Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z . Na mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy jest porównywanie jej elementów parami. Operacja porównania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy , potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Operacją tą będzie operacja polegająca na zamianie elementów w tablicy z pozycji oraz , .

Sortowanie bąbelkowe (BubbleSort)

Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w fazach. W fazie -tej wyznaczany jest -ty najmniejszy element. Załóżmy, że po pierwszych fazach mamy wyznaczone i uporządkowane najmniejsze elementy, tzn. i dla każdego mamy . W fazie -tej porównywane są kolejno elementy w parach , , ..., . Jeżeli elementy w parze nie są uporządkowane, dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.

Algorytm Sortowanie bąbelkowe


 BubbleSort
 1  for  to  do
 2    for   downto  do
 3    if  then
 4      ;

Poniżej zilustrowano działanie sortowania bąbelkowego.

<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300"> alg=BubbleSort delay=1000 </applet>



Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: w pierwszej fazie, w drugiej, ..., w fazie ostatniej, co daje łącznie porównań. Liczba zamian może się zmieniać od do Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 jest taka modyfikacja algorytmu, aby zakończyć jego działanie, kiedy tylko zostanie stwierdzone, że tablica jest już uporządkowana.


Ćwiczenie 1

Zmodyfikuj algorytm sortowania bąbelkowego w taki sposób, żeby jego wykonywanie kończyło się z chwilą stwierdzenia, że tablica jest już posortowana.

Odpowiedź do ćwiczenia 1

Sortowanie przez wybór (SelectionSort)

Na sortowanie bąbelkowe można spojrzeć jeszcze inaczej. W każdej fazie przepychamy na pierwsze miejsce w nieuporządkowanej części tablicy element najmniejszy. Symetrycznie moglibyśmy sortować poczynając od elementów nawiększych. W sortowaniu przez wybór nie przepychamy elementu największego (najmniejszego) na jego miejsce w ciągu uporządkowanym, tylko znajdujemy jego pozycję, a następnie znaleziony element - największy w części nieuporządkowanej - zamieniamy z elementem, który znajduje się na docelowej pozycji elementu największego. Niech będzie funkcją, której wartością jest pozycja największego elementu w podtablicy . Oto schemat algorytmu sortowania przez wybór:

Algorytm Schemat algorytmu sortowania przez wybór


 schemat SelectionSort 
 1  for  downto  do
 2  begin
 3    ;
 4    
 5  end;

Dlaczego użyliśmy słowa schemat? Zauważmy, że do pełnego zdefinowania algorytmu, a także dla jego analizy, niezbędne jest zdefiniowanie funkcji . W klasycznym sortowaniu przez wybór pozycję elementu największego w podtablicy wyznaczamy przeszukując podtablicę od lewej do prawej, pamiętając w zmiennej pomocniczej pozycję dotychczas największego elementu i modyfikując wartość tej zmiennej każdorazowo po napotkaniu elementu większego od dotychczas największego. Oto pełny zapis algorytmu sortowania przez wybór - algorytmu SelectionSort.

Algorytm Sortowanie przez wybór


 SelectionSort
 1  for  downto  do
 2  begin
 3    ;
 4    for  to  do
 5      if  then ;
 6    
 7  end;

Nietrudno zauważyć, że algorytm SelectionSort wykonuje taką samą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko . Poniższa animacja ilustruje działanie algorytmu SelectionSort.

<applet code="SortItem" archive="images/a/a5/Sort2.jar" width="300" height="300"> alg=SelectionSort delay=1000 </applet>




Należy podkreślić, że w implementacji schematu sortowania przez wybór mamy swobodę w realizacji funkcji . Wykorzystamy to w algorytmie sortowania z użyciem struktury danych zwanej kopcem.

Sortowanie przez wstawianie

Sortowanie przez wstawianie jest algorytmem szczególnie polecanym do sortowania krótkich ciągów. Jego złożoność pesymistyczna jest asymptotycznie taka sama jak dwóch poprzednich algorytmów, ale zachowuje się on znacznie lepiej dla ciągów "prawie" posortowanych. Co znaczy "prawie" wyjaśnimy w dalszej części wykładu.

Idea sortowania przez wstawianie jest następująca. Sortujemy w fazach, ponumerowanych dla wygody opisu od 2 do . Przed rozpoczęciem -tej fazy wiemy, że podtablica jest już posortowana. Naszym celem jest uporządkowanie podtablicy , co w rzeczywistości oznacza wstawienie na właściwe miejsce elementu w uporządkowany ciąg . W tym celu odkładamy element z pozycji na bok (zapamiętujemy w pomocniczej zmiennej), a następnie przeglądamy elementy podtablicy od prawej do lewej, przesuwając każdy element większy od odłożonego o jedną pozycję w prawo. Po napotkaniu w tablicy elementu nie większego od elementu odłożonego (nazwijmy go elementem blokującym), element odłożony wstawiany tuż przed element blokujący. Oto zapis sortowania przez wstawianie - algorytm InsertionSort.

Algorytm Sortowanie przez wstawianie


 InsertionSort
 1  for  to  do
 2  begin
 3    // jest już posortowana
 4    ; //odkładamy element z pozycji 
 5    ;
 6    while  do
 7    begin
 8      ; //przesuwamy element większy od  o jedną pozycję w prawo    
 9      
 10   end;
 11    
 12 end;

Poniższa animacja ilustruje działanie sortowania przez wstawianie.

<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300"> alg=InsertionSort delay=1000 </applet>



Dokonamy teraz wspólnie analizy przedstawionego algorytmu. W tym celu postaraj się drogi czytelniku samodzielnie wykonać następujące ćwiczenia.


Ćwiczenie 2

Jakie znaczenie dla poprawności algorytmu InsertionSort ma założenie z początku wykładu o tym, że , dla każdego ?

Odpowiedź do ćwiczenia 2

Ćwiczenie 3

Załóżmy, że sortujemy permutację liczb . Podaj permutacje, dla których algorytm InsertionSort wykona odpowiednio najwięcej i najmniej porównań, a następnie wyznacz dokładne liczby porównań w najgorszym i najlepszym przypadku. Uwaga: pamiętaj o porównaniach z .

Odpowiedź do ćwiczenia 3

Zastanówmy się, od czego zależy liczba porównań wykonywanych przez algorytm InsertionSort dla ustalonej permutacji . W tym celu zdefiniujmy pojęcie inwersji w permutacji. Inwersją w permutacji nazywamy każdą parę indeksów takich, że .

Ćwiczenie 4

Zastanów się, jaka jest zależność pomiędzy liczbą porównań wykonywanych przez algorytm InsertionSort dla permutacji a liczbą inwersji w tej permutacji.

Odpowiedź do ćwiczenia 4

Jedną z miar uporządkowania ciągu elementów jest liczba inwersji w nim występujących. Permutacja rosnąca nie zawiera wcale inwersji, natomiast permutacja malejąca zawiera inwersji. Na podstawie ćwiczenia 4 wnioskujemy, że jeżeli ciąg wejściowy zawiera liniową ze względu na liczbę inwersji, to dla takiego ciągu algorytm InsertionSort działa w czasie liniowym. Jeżeli jednak w ciągu wejściowym jest kwadratowa liczba inwersji, to algorytm InsertionSort działa w czasie kwadratowym. Może jednak takie dane są niesłychanie rzadkie, a dla "przeciętnych" danych algorytm InsertionSort zachowuje się zdecydowanie lepiej? Niestety, to nie jest prawda. Żeby to wykazać, obliczymy oczekiwaną liczbę porównań wykonywanych przez nasz algorytm dla "losowych" danych. Pisząc "losowych", musimy precyzyjnie określić, co mamy na myśli. Dla naszych rozważań przyjmiemy model losowej permutacji, w którym to zakłada się, że początkową zawartością sortowanej tablicy jest permutacja liczb i każda z permutacji może pojawić się z tym samym prawdopodobieństwem . Jeśli już ustaliliśmy model probabilistyczny, to możemy określić średnią liczbę porównań wykonywanych przez algorytm InsertionSort. Nietrudno zauważyć, że wynosi ona



W powyższym wzorze wartość wyrażenia jest równa oczekiwanej liczbie inwersji w losowej permutacji. Żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy więc wyznaczyć oczekiwaną liczbę inwersji w losowej permutacji.

Wektorem inwersji dla permutacji nazywamy ciąg liczb taki, że , dla każdego . Innymi słowy, jest liczbą tych elementów permutacji , która znajdują się na lewo od elementu i są od niego większe.

Ćwiczenie 5

Podaj wektor inwersji dla permutacji .

Odpowiedź do ćwiczenia 5


Nietrudno jest pokazać, że dwóm różnym permutacjom odpowiadają różne wektory inwersji. __

Zauważmy, że elementy każdego wektora inwersji muszą spełniać nierówności , dla . Oznaczmy zbiór wszystkich -elementowych wektorów o takich własnościach przez . Liczba elementów zbioru wynosi . Z naszych dotychczasowych rozważań wynika, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami liczb , a wektorami z . Dlatego elementy tego zbioru będziemy nazywali po prostu wektorami inwersji.

Ćwiczenie 6

Podaj permutację o wektorze inwersji .

Odpowiedź do ćwiczenia 6

Ćwiczenie 7

Zaproponuj algorytm, który dla danego wektora inwersji znajdzie odpowiadającą mu permutację.

Wskazówka do ćwiczenia 7

Odpowiedź do ćwiczenia 7

Sumą wektora inwersji nazwiemy sumę jego elementów. Z dotychczasowych rozważań wynika, że suma wektora inwersji jest równa liczbie inwersji w odpowiadającej temu wektorowi permutacji. Losowy wektor inwersji można otrzymać losując każdy jego element niezależnie w ten sposób, że na pozycji -tej może pojawić się każda z wartości z jednakowym prawdopodobieństwem . Tak więc oczekiwana wartość -tego elementu w losowym wektorze inwersji wynosi . Z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana suma losowego wektora inwersji wynosi . Zatem taka jest też oczekiwana liczba inwersji w losowej permutacji. Wynika stąd, że algorytm sortowania przez wstawianie zachowuje się dla "przeciętnych" danych podobnie, jak dla danych "najgorszych" i działa w czasie kwadratowym.