Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemDaną listę dwukierunkową należy posortować rosnąco algorytmem Quick Sort. |
Wynalazcą algorytmu Quick Sort jest prof. Tony Hoare. Algorytm ten sortuje zbiór danych przy złożoności obliczeniowej O (n log n). Jednakże w pewnych niekorzystnych wypadkach jego złożoność może się degradować do O (n2). Algorytm Quick Sort działa następująco:
Piwot dzieli listę na dwie części, które będziemy nazywać lewą partycją (elementy mniejsze) i prawą partycją (elementy równe lub większe). Zwróć uwagę, że po tej operacji piwot zajął na liście swoją końcową pozycję. Teraz w ten sam sposób sortujemy lewą i prawą partycję. Operacje wykonujemy rekurencyjnie dotąd, aż dojdziemy do partycji pustych lub jednoelementowych. Ponieważ fizycznie nie musimy rozłączać listy, to po wykonaniu tej procedury stanie się ona posortowana, ponieważ każdy podział partycji częściowo porządkuje listę.
Należy rozwiązać kilka problemów technicznych. Po pierwsze, jak wybrać piwot? Najlepszym rozwiązaniem byłoby wybieranie go w sposób losowy wewnątrz listy. Możemy też ułatwić sobie sprawę i jako piwot wybierać pierwszy lub ostatni element listy. Jeśli lista jest nieuporządkowana, to taki sposób wyboru piwota jest zupełnie wystarczający.
Jeśli wybierzemy piwot na początku listy, to podział na partycje uzyskamy przechodząc przez elementy następne aż do końca listy, a następnie porównując je z piwotem. Jeśli dany element jest mniejszy od pivota, to odłączamy go od listy i dołączamy przed pivota. W efekcie w prawej partycji pozostaną tylko elementy większe lub równe piwotowi. Elementy mniejsze zostaną przeniesione do partycji lewej.
Drugim problemem jest podział listy na dwie partycje. Osiągniemy to dodając na początku i na końcu listy elementy będące wartownikami.
Po wybraniu pivota elementy mniejsze dopisujemy przed piwotem. Listę przeszukujemy aż do natrafienia na wartownika prawego. Dalsze podziały listy na partycje nie wymagają już dodawania nowych wartowników – staną się nimi piwoty i poprzedni wartownicy:
Partycja jest pusta, jeśli następnikiem lewego wartownika jest wartownik prawy. Partycja jest jednoelementowa, jeśli następnikiem piwota będzie prawy wartownik. Te spostrzeżenia pozwolą nam zakończyć rekurencję.
Po posortowaniu listy usuwamy z niej pierwszy i ostatni element, czyli
dodanych na początku wartowników.
L | : | zmienna obsługująca listę |
posortowana rosnąco lista obsługiwana przez zmienną L
K01: | Jeśli L.count < 2, to zakończ |
listy pustej i jednoelementowej nie sortujemy |
K02: | Dodaj dowolny element na początek listy | lewy wartownik |
K03: | Dodaj dowolny element na koniec listy | prawy wartownik |
K04: | Partycja (L.head, L.tail) | dziel na partycje, w efekcie sortując listę |
K05: | Usuń pierwszy element | pozbądź się wartowników |
K06: | Usuń ostatni element | |
K07: | Zakończ |
Lw, Pw | : | lewy i prawy wartownik |
posortowana rosnąco partycja pomiędzy elementami wskazywanymi przez Lw oraz Pw.
p | : | pivot |
i, j | : | wskaźniki elementów listy |
K01: | p ← (Lw→next) | ustawiamy piwot na pierwszy element listy |
K02: | i ← (p→next) | i rozpoczyna jako następnik p |
K03: | Jeśli i = Pw, to zakończ |
partycja jest jednoelementowa, kończymy |
K04: | j ← i | j jest badanym elementem |
K05 | i ← (i→next) | i jest zawsze następnikiem |
K06: | Jeśli (j→data) ≥ (p→data), to idź do kroku K13 |
szukamy elementu mniejszego od piwota, pomijając elementy większe lub równe |
K07: | (j→prev→next) ← (j→next) | gdy go znajdziemy, to wyłączamy z listy |
K08: | (j→next→prev) ← (j→prev) | |
K09: | (j→next) ← p | i dołączamy przed piwotem p |
K10: | (j→prev) ← (p→prev) | |
K11: | (p→prev) ← j | |
K12: | (j→prev→next) ← j | |
K13: | Jeśli i
≠
Pw, to idź do kroku K04 |
jeśli nie przetworzyliśmy całej partycji, to wracamy na początek pętli |
K14: | Jeśli Lw→next
≠ p, to Partycja (Lw, p) |
rekurencyjnie dzielimy dalej lewą partycję |
K15: | Jeśli p→next
≠ Pw, to Partycja (p, Pw) |
i prawą partycje |
K16: | Zakończ |
Uwaga: podany algorytm sortowania szybkiego jest jednym z wielu możliwych. Zmiany dotyczą głównie sposobów wyboru piwota oraz przeszukiwania partycji.
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program tworzy listę 200 pseudolosowych liczb całkowitych, po czym sortuje ją algorytmem Quick Sort. Program wykorzystuje obiekt listy dwukierunkowej, w którym typ danych zmieniliśmy ze znakowego na całkowity. W obiekcie pozostawiliśmy jedynie niezbędne metody. |
Pascal// Sortowanie szybkie listy dwukierunkowej // Data: 08.07.2012 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program dlist_qsort; // Definicje typów //---------------- type PdlistEl = ^dlistEl; // wskaźnik do elementów listy // Element listy //-------------- dlistEl = record next : PdlistEl; // następnik prev : PdlistEl; // poprzednik data : integer; end; // Definicja obiektu listy dwukierunkowej //--------------------------------------- dlist = object public head : PdlistEl; // początek listy tail : PdlistEl; // koniec listy count : cardinal; // licznik elementów constructor init; destructor destroy; procedure printl; procedure push_front (v : integer); procedure push_back (v : integer); procedure remove (e : PdlistEl); procedure pop_front; procedure pop_back; procedure quick_sort; procedure partition (Lw, Pw : PdlistEl); end; //--------------------------------------------- // Definicje metod obiektu listy dwukierunkowej //--------------------------------------------- // Inicjuje pola zmiennej listy //----------------------------- constructor dlist.init; begin head := nil; tail := nil; count := 0; end; // Usuwa elementy listy //--------------------- destructor dlist.destroy; begin while count > 0 do pop_front; end; // Procedura wyświetla zawartość elementów listy //---------------------------------------------- procedure dlist.printl; var p : PdlistEl; begin p := head; while p <> NIL do begin write (p^.data : 4); p := p^.next; end; writeln; end; // Procedura dodaje nowy element na początek listy //------------------------------------------------ procedure dlist.push_front (v : integer); var p : PdlistEl; begin new (p); // tworzymy nowy element p^.data := v; p^.prev := nil; p^.next := head; head := p; inc (count); if p^.next <> nil then p^.next^.prev := p else tail := p; end; // Procedura dodaje nowy element na koniec listy //---------------------------------------------- procedure dlist.push_back (v : integer); var p : PdlistEl; begin new (p); // tworzymy nowy element p^.data := v; p^.next := nil; p^.prev := tail; tail := p; inc (count); if p^.prev <> nil then p^.prev^.next := p else head := p; end; // Procedura usuwa wybrany element z listy //---------------------------------------- procedure dlist.remove (e : PdlistEl); begin dec (count); if e^.prev <> nil then e^.prev^.next := e^.next else head := e^.next; if e^.next <> nil then e^.next^.prev := e^.prev else tail := e^.prev; dispose (e); end; // Procedura usuwa element z początku listy //----------------------------------------- procedure dlist.pop_front; begin if count > 0 then remove (head); end; // Procedura usuwa element z końca listy //-------------------------------------- procedure dlist.pop_back; begin if count > 0 then remove (tail); end; // Procedura szybkiego sortowania //------------------------------- procedure dlist.quick_sort; begin if count > 1 then begin push_front (0); // dodajemy lewego wartownika push_back (0); // dodajemy prawego wartownika partition (head, tail); // tworzymy partycje pop_back; // usuwamy prawego wartownika pop_front; // usuwamy lewego wartownika end; end; // Procedura dokonuje rekurencyjnego podziału na partycje //------------------------------------------------------- procedure dlist.partition (Lw, Pw : PdlistEl); var p, i, j : PdlistEl; begin p := Lw^.next; // piwot i := p^.next; if i <> Pw then begin repeat // szukamy elementów mniejszych od piwota j := i; i := i^.next; if(j^.data) < (p^.data) then begin j^.prev^.next := j^.next; // znaleziony element wyciagamy z listy j^.next^.prev := j^.prev; j^.next := p; // i umieszczamy go przed piwotem j^.prev := p^.prev; p^.prev := j; j^.prev^.next := j; end; until i = Pw; if Lw^.next <> p then partition (Lw, p); if p^.next <> Pw then partition (p, Pw); end; end; //--------------- // Program główny //--------------- var L : dlist; begin randomize; L.init; while L.count < 200 do L.push_back (random (101) - 50); L.printl; L.quick_sort; writeln; L.printl; L.destroy; end. |
// Sortowanie szybkie listy dwukierunkowej // Data: 08.07.2012 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // Element listy //-------------- struct dlistEl { dlistEl * next; // następnik dlistEl * prev; // poprzednik int data; }; // Definicja obiektu listy dwukierunkowej //--------------------------------------- class dlist { public: dlistEl * head; // początek listy dlistEl * tail; // koniec listy unsigned count; // licznik elementów dlist(); // konstruktor ~dlist(); // destruktor void printl(); void push_front (int v); void push_back (int v); void remove (dlistEl * e); void quick_sort(); void partition (dlistEl * Lw, dlistEl * Pw); void pop_front(); void pop_back(); }; //------------------------------------ // Metody obiektu listy dwukierunkowej //------------------------------------ // Inicjuje pola zmiennej listy //----------------------------- dlist::dlist() { head = tail = NULL; count = 0; } // Usuwa listę z pamięci //---------------------- dlist::~dlist() { while(count) pop_front(); } // Wyświetla zawartość elementów listy //---------------------------------------------- void dlist::printl() { dlistEl * p; p = head; while(p) { cout << setw (4) << p->data; p = p->next; } cout << endl; } // Dodaje nowy element na początek listy //------------------------------------------------ void dlist::push_front (int v) { dlistEl * p; p = new dlistEl; p->data = v; p->prev = NULL; p->next = head; head = p; count++; if(p->next) p->next->prev = p; else tail = p; } // Dodaje nowy element na koniec listy //---------------------------------------------- void dlist::push_back (int v) { dlistEl * p; p = new dlistEl; p->data = v; p->next = NULL; p->prev = tail; tail = p; count++; if(p->prev) p->prev->next = p; else head = p; } // Usuwa wybrany element z listy //------------------------------ void dlist::remove (dlistEl * e) { count--; if(e->prev) e->prev->next = e->next; else head = e->next; if(e->next) e->next->prev = e->prev; else tail = e->prev; delete e; } // Usuwa element z początku listy //------------------------------- void dlist::pop_front() { if(count) remove (head); } // Usuwa element z końca listy //---------------------------- void dlist::pop_back() { if(count) remove (tail); } // Procedura szybkiego sortowania //------------------------------- void dlist::quick_sort() { if(count > 1) { push_front (0); // dodajemy lewego wartownika push_back (0); // dodajemy prawego wartownika partition (head, tail); // tworzymy partycje pop_back(); // usuwamy prawego wartownika pop_front(); // usuwamy lewego wartownika } } // Procedura dokonuje rekurencyjnego podziału na partycje //------------------------------------------------------- void dlist::partition (dlistEl * Lw, dlistEl * Pw) { dlistEl * p, * i, * j; p = Lw->next; // piwot i = p->next; if(i != Pw) { do // szukamy elementów mniejszych od piwota { j = i; i = i->next; if(j->data < p->data) { j->prev->next = j->next; // znaleziony element wyciagamy z listy j->next->prev = j->prev; j->next = p; // i umieszczamy go przed piwotem j->prev = p->prev; p->prev = j; j->prev->next = j; } } while(i != Pw); if(Lw->next != p) partition (Lw, p); if(p->next != Pw) partition (p, Pw); } } //--------------- // Program główny //--------------- int main() { dlist L; srand (time(NULL)); while(L.count < 200) L.push_back ((rand()% 101) - 50); L.printl(); L.quick_sort(); cout << endl; L.printl(); return 0; } |
Basic' Sortowanie szybkie listy dwukierunkowej ' Data: 08.07.2012 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- ' Element listy '-------------- Type dlistEl next As dlistEl Ptr ' następnik prev As dlistEl Ptr ' poprzednik data As Integer End Type ' Typ obiektowy listy dwukierunkowej '----------------------------------- Type dlist head As dlistEl Ptr ' początek listy tail As dlistEl Ptr ' koniec listy count As UInteger ' licznik elementów Declare Constructor() Declare Destructor() Declare Sub printl() Declare Sub push_front (v As Integer) Declare Sub push_back (v As Integer) Declare Sub remove (e As dlistEl Ptr) Declare Sub pop_front() Declare Sub pop_back() Declare Sub quick_sort() Declare Sub partition (ByVal Lw As dlistEl Ptr, ByVal Pw As dlistEl Ptr) End Type ' Konstruktor listy '------------------ Constructor dlist() head = 0 tail = 0 count = 0 End Constructor ' Usuwa listę z pamięci '---------------------- Destructor dlist() While count > 0 pop_front() Wend End Destructor ' Procedura wyświetla zawartość elementów listy '---------------------------------------------- Sub dlist.printl() Dim p As dlistEl Ptr p = head while p Print Using "####";p->Data; p = p->next Wend Print End Sub ' Procedura dodaje nowy element na początek listy '------------------------------------------------ Sub dlist.push_front (v As Integer) Dim p As dlistEl Ptr p = New dlistEl p->data = v p->prev = 0 p->next = head head = p count += 1 If p->next Then p->next->prev = p Else tail = p End If End Sub ' Procedura dodaje nowy element na koniec listy '---------------------------------------------- Sub dlist.push_back (v As Integer) Dim p As dlistEl Ptr p = New dlistEl p->data = v p->next = 0 p->prev = tail tail = p count += 1 If p->prev Then p->prev->next = p Else head = p End If End Sub ' Procedura usuwa wybrany element z listy '---------------------------------------- Sub dlist.remove (e As dlistEl Ptr) count -= 1 If e->prev Then e->prev->next = e->next Else head = e->next End If If e->next Then e->next->prev = e->prev Else tail = e->prev End If Delete e End Sub ' Procedura usuwa element z początku listy '----------------------------------------- Sub dlist.pop_front() If count > 0 Then remove (head) End Sub ' Procedura usuwa element z końca listy '-------------------------------------- Sub dlist.pop_back() If count > 0 Then remove (tail) End Sub ' Procedura szybkiego sortowania '------------------------------- sub dlist.quick_sort() If count > 1 Then push_front (0) ' dodajemy lewego wartownika push_back (0) ' dodajemy prawego wartownika partition (head, tail) ' tworzymy partycje pop_back() ' usuwamy prawego wartownika pop_front() ' usuwamy lewego wartownika End If End Sub ' Procedura dokonuje rekurencyjnego podziału na partycje '------------------------------------------------------- sub dlist.partition (ByVal Lw As dlistEl Ptr, ByVal Pw As dlistEl Ptr) Dim As dlistEl Ptr p, i, j p = Lw->next ' piwot i = p->Next If i <> Pw Then Do ' szukamy elementów mniejszych od piwota j = i i = i->Next if j->data < p->Data Then j->prev->next = j->next ' znaleziony element wyciagamy z listy j->next->prev = j->prev j->next = p ' i umieszczamy go przed piwotem j->prev = p->prev p->prev = j j->prev->next = j End If Loop Until i = Pw If Lw->next <> p then partition (Lw, p) If p->next <> Pw Then partition (p, Pw) End If End Sub '--------------- ' Program główny '--------------- Dim L As dlist Randomize while L.count < 200: L.push_back (Int (Rnd * 101) - 50): Wend L.printl() L.quick_sort() Print L.printl() End |
Wynik: |
-10 -35 10 -30 -25
20 27 -21 8 -14 25 -49 30 28
37 13 23 -46 15 -46 14 -11 45 -31 -20 13 37 10 1 -24 36 -7 10 20 -7 1 -17 33 7 23 8 16 -4 3 41 31 -8 20 27 -43 36 -43 -3 4 -37 -18 -40 -50 -29 25 5 10 -50 -11 -5 33 -42 -23 42 19 25 19 -3 13 16 -26 8 29 36 -4 -26 -7 -27 -30 29 46 50 -47 14 16 -46 -29 21 44 14 -42 -14 44 -2 6 -24 46 33 12 -42 6 -24 -38 8 -33 -2 -42 26 5 -43 28 7 -10 25 13 -22 -29 -39 21 50 -13 -23 -1 41 48 22 10 4 -49 2 -35 35 40 -6 -23 41 49 -16 36 -33 -37 -37 -31 6 -14 -39 -22 25 -45 -8 47 -22 37 22 23 26 31 -42 -14 -34 26 -47 -1 -32 -14 -31 9 -47 31 -27 -10 -8 10 -7 -21 -37 -25 24 -5 22 -41 -20 12 23 17 -21 41 49 40 -29 -17 18 -38 -33 12 -50 -50 -49 -49 -47 -47 -47 -46 -46 -46 -45 -43 -43 -43 -42 -42 -42 -42 -42 -41 -40 -39 -39 -38 -38 -37 -37 -37 -37 -35 -35 -34 -33 -33 -33 -32 -31 -31 -31 -30 -30 -29 -29 -29 -29 -27 -27 -26 -26 -25 -25 -24 -24 -24 -23 -23 -23 -22 -22 -22 -21 -21 -21 -20 -20 -18 -17 -17 -16 -14 -14 -14 -14 -14 -13 -11 -11 -10 -10 -10 -8 -8 -8 -7 -7 -7 -7 -6 -5 -5 -4 -4 -3 -3 -2 -2 -1 -1 1 1 2 3 4 4 5 5 6 6 6 7 7 8 8 8 8 9 10 10 10 10 10 10 12 12 12 13 13 13 13 14 14 14 15 16 16 16 17 18 19 19 20 20 20 21 21 22 22 22 23 23 23 23 24 25 25 25 25 25 26 26 26 27 27 28 28 29 29 30 31 31 31 33 33 33 35 36 36 36 36 37 37 37 40 40 41 41 41 41 42 44 44 45 46 46 47 48 49 49 50 50 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.