Lemur zaprasza
CIĄG DALSZY ALGORYTMÓW SORTOWANIA Sortowanie przez proste wybieranie Sortowanie przez prostą zamianę Sortowanie mieszane Sortowanie przez podział Sortowanie przez proste wybieranie.Przyjmijmy w procesie sortowania następującą zasadę: wybieramy obiekt o najmniejszym kluczu, wymieniamy go z pierwszym obiektem a1. Operacje te powtarzamy kolejno z pozostałymi n-l, n-2 obiektami do momentu, gdy pozostanie tylko jeden, największy obiekt. Algorytm realizujący tę strategię przedstawiony jest poniżej: for i:=1 to n-l do begin " przypisz k indeks najmniejszego obiektu wsrod a[i]..a[n] " " dokonaj zamiany a[i] i a[k] " end Ilustruje to poniższy przykład: i=1 ^44 55 12 42 94 18 06 67 i=2 06 ^55 12 42 94 18 44 67 i=3 06 12 ^55 42 94 18 44 67 i=4 06 12 18 ^42 94 55 44 67 i=5 06 12 18 42 ^94 55 44 67 i=6 06 12 18 42 44 ^55 94 67 i=7 06 12 18 42 44 55 ^94 67 i=8 06 12 18 42 44 55 67 ^94Metoda prostego wybierania jest w pewnym sensie odwrotna do prostego wstawiania. W metodzie prostego wstawiania w każdym kroku rozważa się jeden obiekt ciągu źródłowego i wszystkie obiekty tablicy wynikowej; w metodzie prostego wybierania rozważa się wszystkie elementy tablicy źródłowej, wybiera ten z najmniejszym kluczem by wstawić go w określone miejsce ciągu wynikowego. Mamy więc do czynienia ze zmniejszeniem liczby przestawień. Procedura realizująca ten algorytm przedstawiona jest poniżej: procedure ProsteWybieranie; var i,j,k : Indeks; x : Obiekt; begin for i:=l to n-l do { petle po pozycjach, na ktore przestawiamy } begin k:=i; { startowy indeks najmniejszego wyrazu } x:=a[i]; { startowa wartosoc najmniejszego wyrazu } for j:=i+l to n do { petla przemieszczania sie po tablicy } if a[j].Klucz<x.Klucz then { czy znaleziono mniejszy wyraz } begin { jezeli znaleziono to wtedy. . . } k:=j; { indeks aktualnie najmniejszego } x:=a[j] { wartosc aktualnie najmniejszego } end; a[k]:=a[i]; { wyraz i-ty na miejsce najmniejszego } a[i]:=x { najmniejszy przechodzi na i-ta pozycje } end end;Algorytm ten jest przeważnie lepszy od prostego wstawiania, chociaż w wypadkach, w których klucze są choćby częściowo posortowane, wstawianie proste jest ciągle nieco szybsze. Nie istnieje jednoznaczna klasyfikacja metod sortowania. Omówione poprzednie techniki bazują na zamianie, prezentowana poniżej ma podobny punkt wyjścia, tj. zamianę dwóch obiektów. Dotyczy to jednak obiektów bezpośrednio ze sobą sąsiadujących. Proces powtarzany jest dopóki nie zostaną posortowane wszystkie elementy. Nosi on nazwę... Sortowania przez prostą zamianę (bąbelkowego)Sortowanie babelkowe polega na powtarzaniu przejścia przez tablicę i przesuwaniu za każdym razem najmniejszego z pozostałych obiektów na jej lewy koniec (początek). Jeżeli "obrócimy" tablicę o 90° (lewy koniec do góry) możemy podać prostą i zabawną interpretację zachodzącego procesu. Najmniejsze (najlżejsze) elementy będą przesuwać się do góry jak bąbelki w naczyniu z cieczą, najcięższe (największe) będą opadać na dno. Procedura realizująca ten algorytm ma prostą budowę. procedure SortowanieBabelkowe; var i,j : Indeks; x : Obiekt; begin for i:=2 to n do { kolejne przegladania tablicy } begin for j: =n downto i do { przegladamy tablice od samego dolu } if a[j-l].Klucz>a[j].Klucz then { czy wyzszy jest wiekszy? } begin { jezeli tak, to bedziemy go "spychac" w dol } x:=a[j-l]; { ten wyraz pojdzie oczko do dolu } a[j-l]:=a[j]; { babelek idzie do gory o oczko w gore ... } a[j]:=x { ten wyraz z kolei "opada" do dolu } end { koniec pojedynczego " spychania" i awansu w gore } end end; Ilustracją tego algorytmu będzie nasz stały przykład wzorcowy obrócony o 90o start i=2 i=3 i=4 i=5 i=6 i=7 i=8 44 44 44 44 44 44 44 06 06 06 06 06 06 06 06 55 55 55 55 55 55 06 44 12 12 12 12 12 12 12 12 12 12 12 12 06 55 55 44 18 18 18 18 18 18 42 42 42 42 06 12 12 12 55 44 42 42 42 42 42 94 94 94 06 42 42 42 42 18 44 44 44 44 44 44 18 18 06 94 94 94 94 94 42 55 55 55 55 55 55 06 06 18 18 18 18 18 18 94 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 94 94 94 94 94 94 j=8 j=7 j=6 j=5 j=4 j=3 j=2 Istnieje powiedzenie, rozpowszechnione wśród informatyków, że każdy, absolutnie każdy, program można poprawić. Łatwo spostrzec, że trzy ostatnie przejścia w analizowanym przykładzie nie mają żadnego wpływu na kolejność obiektów - są one już po prostu posortowane. Pierwsze usprawnienie algorytmu przyniesie nam zapamiętanie, czy dokonano w czasie danego przejścia zmian czy nie. Przejście bez zmian oznacza, że można zakończyć wykonywanie algorytmu. Drugie, dodatkowe usprawnienie, to zapamiętanie nie tylko samego faktu ale także pozycji ostatniej zamiany. Będzie można dzięki temu zakończyć kolejne przejście wcześniej niż na indeksie i. Trzecie usprawnienie, to zmiana kierunków kolejnych przejść. Fakt ten jest następstwem swoistej asymetrii występującej podczas sortowania i wymagającej szerszego omówienia. Wyobraźmy sobie tylko jeden źle ustawiony wyraz: mały w ciężkim końcu (tu wystarczy jedno przejscie!!!) 12 18 42 44 55 67 94 06 duży w lekkim końcu (tu potrzeba aż siedmiu przejsć!!!) 94 06 12 18 42 44 55 67 Wprowadzenie tych trzech usprawnień prowadzi do algorytmu sortowania mieszanego. Sortowanie mieszane procedure SortowanieMieszane; var j,k,l,p : Indeks; x : Obiekt; begin i:=2; { lewy koniec przedzialu, w ktorym sa zamiany } p:=n; { prawy koniec tego przedzialu } k:=n; { tu zapamietujemy pozycje ostatniej zamiany } repeat { pytanie podstawowe - jak dlugo bedzie trwala zamiana? } for j:=p downto 1 do { petla zamian taka jak w algorytmie babelkowym } if a[j-l].Klucz>a[j].Klucz then { czy "wyzszy" wyraz jest wiekszy } begin { jezeli tak, to wtedy dokonamy zamiany miejscami } x:=a[j-l]; { ten wyraz pojdzie o oczko do dolu } a[j-l]:=a[j]; { lekki babelek idzie o oczko do ggry } a[j]:=x. { ten wyraz z kolei opada oczko do dolu } k:=j; { nowosc! zapamietujemy pozycje przestawienia } end; { koniec zamian "do gory" } l:=k+l; { modyfikacja lewego konca przedzialu przestawien } for j.=l to p do { tu petla zamian "do dolu" - modyfikacja! } if a[j-l].Klucz>a[j].Klucz then { znow: czy "wyzszy" jest wiekszy } begin { jezeli tak, to bedzie zamiana miejscami } x:=a[j-l]; { ten wyraz bedzie przestawiany "dg dolu" } a[j-l]:=a[j]; { wedrowka oczko do gory } a[j]:=x; { wedrowka oczko do dolu } k:=j { zapamietanie pozycji przestawienia } end; { koniec zamian "do dolu" } p:=k-l { modyfikujemy prawy koniec przedzialu przestawien } until l>p { dopoki przedzial przestawiania bedzie mial dlugosc >O } end; { czyli innymi slowy dopoki l>p (ten chwyt swietnie znamy) } Funkcjonowanie tego algorytmu ilustruje nasz już prawie klasyczny przykład. l= 2 3 3 4 4 p= 8 8 7 7 4 ^ ^ ^ 1 44 06 06 06 06 2 55 44 44 12 12 3 12 55 12 44 18 4 42 12 42 18 42 5 94 42 55 42 44 6 18 94 18 55 55 7 06 18 67 67 67 8 67 67 94 94 94Dokładna analiza metod sortowania wykazuje, że metoda sortowania przez zamianę jak i jej ulepszenie - metoda mieszana są gorsze od sortowania przez wstawienie i wybieranie. Usprawnienia tych metod w żaden sposób nie wpływają na liczbę przesunięć obiektów. Obniżeniu ulega jedynie liczba porównań. Ponieważ przestawienie jest znacznie kosztowniejsze od porównania często intuicyjnie błyskotliwe usprawnienia mają marginalne znaczenie praktyczne. Średnia odległość, jaką każdy z n sortowanych obiektów musi przebyć wynosi n/3. Fakt ten jest drogowskazem dla poszukiwań efektywnych metod sortowania. W metodach prostych w każdym kroku przesuwa się obiekt de facto o jedno miejsce. Stąd ogólny koszt metody rzędu n2. Ulepszenia muszą opierać się na założeniu przesuwania obiektów w pojedynczym kroku na większą odległość. Sortowanie przez podział.Jedną z najbardziej efektywnych i nowoczesnych metod sortowania jest metoda, w której stosuje się zasadę zamiany. Ulepszenia wprowadzone do metody sortowania przez zamianę dały w efekcie jedną z najlepszych metod sortowania tablic. Ze względu na jej efektywność jej twórca C.A.R. Hoare określił ją mianem sortowania szybkiego. W metodzie tej w celu zapewnienia efektywności zamienia się miejscami obiekty znajdujące się daleko od siebie. Algorytm postępowania jest następujący. wybieramy pewien obiekt x (na przykład środkowy), przeglądamy tablicę od lewej strony, aż znajdziemy obiekt a[i]>x, przeglądamy tablicę od prawej strony, aż znajdziemy obiekt a[j]<x, wymieniamy te dwa obiekty i . . . kontynuujemy proces przeglądania i zamiany aż do spotkania w okolicach środka tablicy. Efektem tego algorytmu będzie tablica podzielona na dwie części: lewą, z kluczami mniejszymi od x, prawą, z kluczami większymi od x. Proces ten realizuje poniższa procedura. procedure Podzial; var i,j : Indeks; { robocze indeksy } x,y : Obiekt; { robocze zmienne typu sortowany obiekt } begin i:=l; { i : = minimalny klucz } j:=n; { j : = maksymalny klucz } x:=a[(l+r) div 2]; { x - wyraz srodkowy sortowanej tablicy } repeat { cala historie bedziemy powtarzac tak dlugo jak ... } while a[i].Klucz < x.Klucz do { dopoki jestesmy na lewo od srodkowego } i:=i+l; { . . . powiekszamy indeks i } while x.Klucz < a[j].Klucz do { dopoki na prawo od srodkowego } j:=j-l; { ... zmniejszamy indeks j } if i<=j then { jezeli i <= j wtedy : } begin { zamieniamy miejscami wyrazy i, j } y:=a[i]; { podstawienie do zmiennej roboczej } a[i]:=a[j]; { pierwszy etap zamiany } a[j]:=y; { drugi etap zamiany } i:=i+1; { zwiekszenie indeksu i } j:=j-1; { zmniejszenie indeksu j } end; until i>j; { nie zostanie spelniony warunek i>j } end. Działanie algorytmu zilustrujemy na klasycznym już przykładzie. Aby otrzymać tablicę podzieloną trzeba dokonać dwóch zamian: 44 55 12 42 94 06 18 67 18 06 12 42 94 55 44 i=5 j=3Efektem działania procedury Podzial jest sytuacja, w której: klucze a[1]. ..a[i-l] są mniejsze bądź równe kluczowi x, klucze a[j-l]...a[n]są większe bądź równe kluczowi x. Otrzymaliśmy więc podział tablicy na dwie części: k=l..i-l a[k].klucz <= x.klucz, k=j+l..n a[k].klucz >= x.klucz oraz k=j+l..i-l a[k].klucz = x.klucz. Algorytm podziału tablicy prowadzi bezpośrednio do posortowania tablicy. Po dokonaniu pierwszego podziału przeprowadzamy ten sam proces dla obu części. Obliczenia kontynuujemy dopóty, dopóki każda z części nie będzie składać się tylko z jednego obiektu. Ten sposób postępowania ilustruje poniższa procedura. procedure SzybkieSortowanie; procedure Sortuj(l, p : Indeks); var i,j : Indeks; { robocze indeksy } x,y : Obiekt; { robocze zmienne typu sortowany obiekt } begin i:=l; { i : = minimalny klucz } j:=n; { j : = maksymalny klucz } x:=a[(l+r) div 2]; { x - wyraz srodkowy sortowanej tablicy } repeat { cala historie bedziemy powtarzac tak dlugo jak . . . } while a[i].Klucz < x.Klucz do { dopoki jestesmy na lewo od srodkowego } i:=i+l; { ...powiekszamy indeks i } while x.Klucz < a[j].Klucz do { dopoki na prawo od srodkowego } j:=j-l; { ...zmniejszamy indeks j } if i<=j then { jezeli i <= j wtedy : } begin { zamieniamy miejscami wyrazy i, j } y:=a[i]; { podstawienie do zmiennej roboczej } a[i]:=a[j]; { pierwszy etap zamiany } a[j]:=y. { drugi etap zamiany } i:=i+l; { zwiekszenie indeksu i } j:=j-l; { zmniejszenie indeksu j } end; until i>j; { nie zostanie spelniony warunek i>j } if 1<j then Sortuj(l, j); if i<p then Sortuj(i, p); end. begin Sortuj(l, n) end. Procedura Sortuj wywołuje siebie rekurencyjnie. Rekurencja jest bardzo silnym narzędziem programistycznym. Ten sam algorytm można zapisać w postaci nierekurencyjnej zastępując rekurencję przez iterację. Na zakończenie rozważań dotyczących algorytmów sortowania porównamy ich efektywność. Wszystkie cytowane procedury zostały zaprojektowane przez autora Pascala, Pana Niklausa Wirtha i pochodzą z książki Algorytmy + struktury danych = programy. Ich działanie testowano na losowym zestawie danych. Wykorzystano mikrokomputer 386DX 40MHz z koprocesorem. Nieco szokujące wyniki czasy obliczeń w sekundach - są zestawione w poniższej tabeli. Liczba elementów 10 100 1000 5000 10000 15000 20000 25000 30000 Proste wstawianie .00 .00 .44 9.83 40.75 91.78 162.53 - - Wstawianie połówkowe .00 .00 .33 8.28 32.84 74.42 132.59 - - Proste wybieranie .00 .00 .71 17.41 69.53 156.37 278.09 - - Sortowanie babelkowe .00 .00 1.16 29.33 117.60 - - - - Sortowanie mieszane .00 .00 .99 24.67 100.29 - - - - Szybkie sortowanie .00 .00 .00 .11 .27 .44 .61 .83 .98Jeszcze raz potwierdziła się prawda, że o efektywności programu zależy przede wszystkim algorytm obliczeń. Można używać coraz szybszych procesorów, szukać lepszych języków programowania i sprawniejszych kompilatorów. Są to jedynie półśrodki. Podstawowe "rezerwy" tkwią jednak ciągle w sposobie wykonywania obliczeń, czyli wykorzystywanym algorytmie. Starałem się Was o tym przekonać na kartach tej książki. Wierzę, że skutecznie. |