Algorytmy i Struktury Danych - Sortowanie szybkie listy dwukierunkowej

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 (n²). Algorytm Quick Sort działa następująco:

Wybieramy na liście jeden element, który nazwiemy piwotem (ang. pivot – element zwrotny). Następnie tak przekształcamy listę, aby elementy większe lub równe piwotowi znalazły się po prawej stronie piwota, a elementy mniejsze po stronie lewej:

obrazek

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.

obrazek

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.

obrazek

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:

obrazek

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.

Algorytm szybkiego sortowania listy dwukierunkowej

Wejście:

zmienna obsługująca listę

Wyjście:

posortowana rosnąco lista obsługiwana przez zmienną L

Lista kroków:

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

Algorytm rekurencyjnego partycjonowania listy

Wejście:

Lw, Pw

lewy i prawy wartownik

Wyjście:

posortowana rosnąco partycja pomiędzy elementami wskazywanymi przez Lw oraz Pw.

Zmienne pomocnicze:

p	:	pivot
i, j	:	wskaźniki elementów listy

Lista kroków:

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.

Przykładowe programy

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.

C++

// 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

Na początek: podrozdziału strony

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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sortowanie szybkie listy dwukierunkowej

Problem

Rozwiązanie

Algorytm szybkiego sortowania listy dwukierunkowej

Wejście:

Wyjście:

Lista kroków:

Algorytm rekurencyjnego partycjonowania listy

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy