Algorytmy i Struktury Danych - Sortowanie szybkie listy dwukierunkowej

Wynalazcą algorytmu Quick Sort jest prof. Tony Hoare. Algorytm ten sortuje zbiór danych w klasie złożoności obliczeniowej O(n·logn). Jednakże w pewnych niekorzystnych wypadkach jego klasa złożoności 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:

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 wartowników.

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.

Algorytm szybkiego sortowania listy dwukierunkowej

Wejście:

L : zmienna listy dwukierunkowej.

Wyjście:

Posortowana rosnąco lista wskazywana przez zmienną L.

Elementy pomocnicze:

l_push_front(X, v) : wstawia nowy element o wartości v na początek listy X.
l_push_back(X, v) : wstawia nowy element o wartości v na koniec listy X.
l_pop_front(X) : usuwa element z początku listy X.
l_pop_back(X) : usuwa element z końca listy X.
l_quicksort(X) : sortuje szybko listę X.
l_partition(lg, rg) : dzieli rekurencyjnie na partycje, lg i rg to adresy lewego i prawego wartownika.

Lista kroków:

l_quicksort(L):

K01: Jeśli L.count < 2, ; listy pustej i jednoelementowej nie sortuj
     to zakończ
K02: l_push_front(L, 0) ; dodaj lewego wartownika
K03: l_push_back(L, 0) ; dodaj prawego wartownika
K04: l_partition(L.head, L.tail) ; dziel na partycje, 
     ; w efekcie sortując listę
K05: l_pop_front(L) ; usuń lewego wartownika
K06: l_pop_back(L) ; usuń prawego wartownika
K07: Zakończ

Algorytm rekurencyjnego partycjonowania listy

Wejście:

lg, rg : lewy i prawy wartownik.

Wyjście:

Posortowana rosnąco partycja pomiędzy elementami wskazywanymi przez lg oraz rg.

Elementy pomocnicze:

p : pivot.
i, j : wskaźniki elementów listy.
l_partition(lg, rg) : dzieli rekurencyjnie na partycje, lg i rg to adresy lewego i prawego wartownika.

Lista kroków:

l_partition(lg, rg):

K01: p ← lg→next ; ustawiamy piwot na pierwszy element listy
K02: Jeśli p = rg, ; partycja jest pusta, kończymy
     to zakończ
K03: i ← p→next ; i rozpoczyna jako następnik piwota
K04: Jeśli i = rg, ; partycja jest jednoelementowa, kończymy
     to zakończ
K05:   j ← i ; j jest badanym elementem
K06    i ← i→next ; i jest zawsze następnikiem
K07:   Jeśli j→data ≥ p→data, ; szukamy elementu mniejszego od piwota, 
       to idź do kroku K14 ; pomijając elementy większe lub równe
K08:   j→prev→next ← j→next ; gdy go znajdziemy, to odłączamy od listy
K09:   j→next→prev ← j→prev
K10:   j→next ← p  ; i dołączamy go przed piwotem p
K11:   j→prev ← p→prev
K12:   p→prev ← j
K13:   j→prev→next ← j
K14:   Jeśli i ≠ rg, ; jeśli nie przetworzyliśmy całej partycji, 
       to idź do kroku K05 ; to wracamy na początek pętli
K15: Jeśli lg→next ≠ p, ; rekurencyjnie dzielimy lewą partycję
     to l_partitionlg, p)
K16: Jeśli p→next ≠ rg, ; i prawą partycje
     to l_partition(p, rg)
K17: 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

  PDLel = ^DLel; // wskaźnik do elementu listy

  // Element listy
  //--------------
  DLel = record
    next : PDLel; // następnik
    prev : PDLel; // poprzednik
    data : integer;
  end;

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
  DLvar = object
    public
      head  : PDLel; // początek listy
      tail  : PDLel; // koniec listy
      count : cardinal; // licznik elementów

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : integer);
      procedure   l_push_back(v : integer);
      procedure   l_remove(e : PDLel);
      procedure   l_pop_front;
      procedure   l_pop_back;
      procedure   l_quicksort;
      procedure   l_partition(lg, rg : PDLel);
  end;

//---------------------------------------------
// Definicje metod obiektu listy dwukierunkowej
//---------------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
constructor DLvar.init;
begin
  head  := nil;
  tail  := nil;
  count := 0;
end;

// Usuwa elementy listy
//---------------------
destructor DLvar.destroy;
begin
  while count > 0 do l_pop_front;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure DLvar.l_print;
var
  p : PDLel;
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 DLvar.l_push_front(v : integer);
var
  p : PDLel;
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 DLvar.l_push_back(v : integer);
var
  p : PDLel;
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 DLvar.l_remove(e : PDLel);
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 DLvar.l_pop_front;
begin
  if count > 0 then
    l_remove(head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure DLvar.l_pop_back;
begin
  if count > 0 then
    l_remove(tail);
end;

// Procedura szybkiego sortowania
//-------------------------------
procedure DLvar.l_quicksort;
begin
  if count > 1 then
  begin
    l_push_front(0); // dodajemy lewego wartownika
    l_push_back(0); // dodajemy prawego wartownika
    l_partition(head, tail); // tworzymy partycje
    l_pop_back; // usuwamy prawego wartownika
    l_pop_front; // usuwamy lewego wartownika
  end;
end;

// Procedura rekurencyjnie dzieli na partycje
//-------------------------------------------
procedure DLvar.l_partition(lg, rg : PDLel);
var
  p, i, j : PDLel;
begin
  p := lg^.next; // piwot
  i := p^.next;
  if (p <> rg) and (i <> rg) 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; // element wycinamy
        j^.next^.prev := j^.prev; // z listy
        j^.next := p; // i wstawiamy go przed piwot
        j^.prev := p^.prev;
        p^.prev := j;
        j^.prev^.next := j;
      end;
    until i = rg;

    if lg^.next <> p then
      l_partition(lg, p);
    if p^.next <> rg then
      l_partition(p, rg);

  end;
end;

//---------------
// Program główny
//---------------

var

  L : DLvar;

begin

  randomize;

  L.init;

  while L.count < 200 do
    L.l_push_back(random(101)-50);
  L.l_print;
  L.l_quicksort;
  writeln;
  L.l_print;

  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 DLel
{
  DLel * next; // następnik
  DLel * prev; // poprzednik
  int data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class DLvar
{
  public:
    DLel * head; // początek listy
    DLel * tail; // koniec listy
    unsigned count; // licznik elementów

    DLvar();     // konstruktor
    ~DLvar();    // destruktor
    void l_print();
    void l_push_front(int v);
    void l_push_back(int v);
    void l_remove(DLel * e);
    void l_quicksort();
    void l_partition(DLel * lg, DLel * rg);
    void l_pop_front();
    void l_pop_back();
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
DLvar::DLvar()
{
  head  = tail  = NULL;
  count = 0;
}

// Usuwa listę z pamięci
//----------------------
DLvar::~DLvar()
{
  while(count) l_pop_front();
}

// Wyświetla zawartość elementów listy
//----------------------------------------------
void DLvar::l_print()
{
  DLel * p;

  p = head;
  while(p)
  {
    cout << setw(4) << p->data;
    p = p->next;
  }
  cout << endl;
}

// Dodaje nowy element na początek listy
//------------------------------------------------
void DLvar::l_push_front(int v)
{
  DLel * p;

  p = new DLel;
  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 DLvar::l_push_back(int v)
{
  DLel * p;

  p = new DLel;
  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 DLvar::l_remove(DLel * 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 DLvar::l_pop_front()
{
  if(count)
    l_remove(head);
}

// Usuwa element z końca listy
//----------------------------
void DLvar::l_pop_back()
{
  if(count)
    l_remove(tail);
}

// Procedura szybkiego sortowania
//-------------------------------
void DLvar::l_quicksort()
{
  if(count > 1)
  {
    l_push_front(0); // dodajemy lewego wartownika
    l_push_back(0);  // dodajemy prawego wartownika
    l_partition(head, tail); // tworzymy partycje
    l_pop_back();    // usuwamy prawego wartownika
    l_pop_front();   // usuwamy lewego wartownika
  }
}

// Rekurencyjny podział na partycje
//---------------------------------
void DLvar::l_partition(DLel * lg, 
                           DLel * rg)
{
  DLel * p, * i, * j;

  p = lg->next; // piwot
  i = p->next;
  if((p != rg) && (i != rg))
  {
    do // szukamy elementów mniejszych od piwota
    {
      j = i;
      i = i->next;
      if(j->data < p->data)
      {
        j->prev->next = j->next; // element wycinamy
        j->next->prev = j->prev; // z listy
        j->next = p; // i wklejamy go przed piwot
        j->prev = p->prev;
        p->prev = j;
        j->prev->next = j;
      }
    } while(i != rg);

    if(lg->next != p)
      l_partition(lg, p);
    if(p->next != rg)
      l_partition(p, rg);
  }
}

//---------------
// Program główny
//---------------

int main()
{
  DLvar L;

  srand(time(NULL));

  while(L.count < 200)
    L.l_push_back((rand()%101)-50);
  L.l_print();
  L.l_quicksort();
  cout << endl;
  L.l_print();

  return 0;
}

Basic

' Sortowanie szybkie listy dwukierunkowej
' Data: 08.07.2012
' (C)2020 mgr Jerzy Wałaszek
'----------------------------------------

' Element listy
'--------------
Type DLel
  next As DLel Ptr   ' następnik
  prev As DLel Ptr   ' poprzednik
  data As Integer
End Type

' Typ obiektowy listy dwukierunkowej
'-----------------------------------
Type DLvar
  head As DLel Ptr ' początek listy
  tail As DLel Ptr ' koniec listy
  count As UInteger   ' licznik elementów

  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As Integer)
  Declare Sub l_push_back(v As Integer)
  Declare Sub l_remove(e As DLel Ptr)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
  Declare Sub l_quicksort()
  Declare Sub l_partition(ByVal lg As DLel Ptr, _
                          ByVal rg As DLel Ptr)
End Type

' Konstruktor listy
'------------------
Constructor DLvar()
  head  = 0
  tail  = 0
  count = 0
End Constructor

' Usuwa listę z pamięci
'----------------------
Destructor DLvar()
  While count > 0
  	 l_pop_front()
  Wend
End Destructor

' Wyświetla zawartość elementów listy
'------------------------------------
Sub DLvar.l_print()
  Dim p As DLel Ptr

  p = head
  while p
    Print Using "####";p->Data;
    p = p->next
  Wend
  Print
End Sub

' Dodaje nowy element na początek listy
'--------------------------------------
Sub DLvar.l_push_front(v As Integer)
  Dim p As DLel Ptr

  p = New DLel
  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

' Dodaje nowy element na koniec listy
'------------------------------------
Sub DLvar.l_push_back(v As Integer)
  Dim p As DLel Ptr

  p = New DLel
  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

' Usuwa wybrany element z listy
'------------------------------
Sub DLvar.l_remove(e As DLel 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

' Usuwa element z początku listy
'-------------------------------
Sub DLvar.l_pop_front()
  If count > 0 Then _
    l_remove(head)
End Sub

' Usuwa element z końca listy
'----------------------------
Sub DLvar.l_pop_back()
  If count > 0 Then _
    l_remove(tail)
End Sub

' Procedura szybkiego sortowania
'-------------------------------
sub DLvar.l_quicksort()
  If count > 1 Then
    l_push_front(0) ' lewy wartownik
    l_push_back(0)  ' prawy wartownik
    l_partition(head, tail) ' tworzymy partycje
    l_pop_back()    ' usuwamy prawego wartownika
    l_pop_front()   ' usuwamy lewego wartownika
  End If
End Sub

' Dokonuje rekurencyjnego podziału na partycje
'---------------------------------------------
sub DLvar.l_partition(ByVal lg As DLel Ptr, _
                         ByVal rg As DLel Ptr)
  Dim As DLel Ptr p, i, j

  p = lg->next ' piwot
  i = p->Next
  If (p <> rg) AndAlso (i <> rg) Then
    Do ' szukamy elementów mniejszych od piwota
      j = i
      i = i->Next
      if j->data < p->Data Then
        j->prev->next = j->next ' element wycinamy
        j->next->prev = j->prev
        j->next = p ' i wklejamy go przed piwotem
        j->prev = p->prev
        p->prev = j
        j->prev->next = j
      End If
    Loop Until i = rg

    If lg->next <> p then _
      l_partition(lg, p)
    If p->next <> rg Then _
      l_partition(p, rg)

  End If
End Sub

'---------------
' Program główny
'---------------

Dim L As DLvar

Randomize

while L.count < 200
  L.l_push_back(Int(Rnd*101)-50)
Wend

L.l_print()
L.l_quicksort()
Print
L.l_print()

End

Python (dodatek)

# Sortowanie szybkie listy dwukierunkowej
# Data: 30.05.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------------------


# klasa elementu listy
# ---------------------
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.data = data


# klasa listy dwukierunkowej
# ---------------------------
class DLvar:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


    # Destructor
    def __del__(self):
        while self.count:
            self.l_pop_front()


    # Wyświetla zawartość elementów listy
    def l_print(self):
        p = self.head
        while p:
            print("%4d" % p.data, end="")
            p = p.next
        print()


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = DLel(v)
        p.next = self.head
        self.head = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p


    # Dodaje nowy element na koniec
    def l_push_back(self, v):
        p = DLel(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p


    # Usuwa wybrany element z listy
    def l_remove(self, e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev


    # Usuwa element z początku
    def l_pop_front(self):
        if self.count:
            self.l_remove(self.head)


    # Usuwa element z końca
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)


    # Szybkie sortowanie
    def l_quicksort(self):
        if self.count > 1:
            self.l_push_front(0)
            self.l_push_back(0)
            self.l_partition(self.head, self.tail)
            self.l_pop_back()
            self.l_pop_front()


    # Rekurencyjny podział na partycje
    def l_partition(self, lg, rg):
        p = lg.next
        i = p.next
        if (p is not rg) and (i is not rg):
            while True:
                j = i
                i = i.next
                if j.data < p.data:
                    j.prev.next = j.next
                    j.next.prev = j.prev
                    j.next = p
                    j.prev = p.prev
                    p.prev = j
                    j.prev.next = j
                if i is rg: break
            if lg.next is not p:
                self.l_partition(lg, p)
            if p.next is not rg:
                self.l_partition(p, rg)


# ---------------
# Program główny
# ---------------

import random

dl = DLvar()
while dl.count < 200:
    dl.l_push_back(random.randrange(-50, 51))
dl.l_print()
dl.l_quicksort()
print()
dl.l_print()

Wynik:

  10  -5  28  18  42 -46  -8  43  19  28  30 -30   7   6   1  38 -50 -10  43  13
 -26  20  14  45  43  42 -42 -21  26  43 -43 -19 -10  36  40  19  18 -10  -5  49
  16  -1  -1 -34 -26 -50 -30 -13 -20 -31  31 -30  -3  10  48 -31 -20  43  -3 -38
  22  48  49 -32  16 -32 -50 -39  10  24 -46 -38 -33  -3  18  13 -47 -36 -47  12
  39  -8 -14   0  44 -38 -20  34 -20   0  44  -5 -44 -14   5  45   1 -32   2 -34
  18 -39  42  -6 -31 -44  47 -14 -32 -20 -13 -26   9  -6 -31  17  24  25   3 -29
 -21  -4  -8  31  13 -40 -28 -25 -27 -38   5 -29 -45 -28 -38 -29 -21 -17 -24 -33
 -28 -32  48 -27 -17 -31  42  17 -22  -6  18  31  44  21 -25 -11  35 -16  15  26
 -15  -1  27 -13  30 -28 -39 -14  27 -31  -3 -18  20  16 -42 -44  49  47  23  -2
 -13 -33 -24  42 -46  -7  44  23  44  14 -33 -10  37 -18  43  46 -36  36  15 -11

 -50 -50 -50 -47 -47 -46 -46 -46 -45 -44 -44 -44 -43 -42 -42 -40 -39 -39 -39 -38
 -38 -38 -38 -38 -36 -36 -34 -34 -33 -33 -33 -33 -32 -32 -32 -32 -32 -31 -31 -31
 -31 -31 -31 -30 -30 -30 -29 -29 -29 -28 -28 -28 -28 -27 -27 -26 -26 -26 -25 -25
 -24 -24 -22 -21 -21 -21 -20 -20 -20 -20 -20 -19 -18 -18 -17 -17 -16 -15 -14 -14
 -14 -14 -13 -13 -13 -13 -11 -11 -10 -10 -10 -10  -8  -8  -8  -7  -6  -6  -6  -5
  -5  -5  -4  -3  -3  -3  -3  -2  -1  -1  -1   0   0   1   1   2   3   5   5   6
   7   9  10  10  10  12  13  13  13  14  14  15  15  16  16  16  17  17  18  18
  18  18  18  19  19  20  20  21  22  23  23  24  24  25  26  26  27  27  28  28
  30  30  31  31  31  34  35  36  36  37  38  39  40  42  42  42  42  42  43  43
  43  43  43  43  44  44  44  44  44  45  45  46  47  47  48  48  48  49  49  49

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:

Elementy pomocnicze:

Lista kroków:

l_quicksort(L):

Algorytm rekurencyjnego partycjonowania listy

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

l_partition(lg, rg):

Przykładowe programy