Sortowanie kubełkowe
           Bucket Sort


Podrozdziały     Tematy pokrewne

Algorytm

Podany w poprzednim rozdziale algorytm sortowania kubełkowego jest bardzo uproszczony i pozwala sortować tylko liczby całkowite. Teraz opiszemy pełny algorytm sortowania kubełkowego pozbawiony tych ograniczeń. Najpierw kilka założeń i definicji:

Sortujemy zbiór d[ ] liczb rzeczywistych. Niech wmin oznacza dolny kres wartości elementów d[ ], a wmax niech oznacza kres górny. Wartości te tworzą przedział liczbowy <wmin, wmax>, w który wpadają wszystkie elementy zbioru. Przedział dzielimy na m segmentów, które nazwiemy kubełkami. W tym celu obliczamy szerokość kubełka:

 

szkb =  wmax - wmin
m

 

Poszczególne kubełki to:

 

dla i = 0,1,...,m: <wmin + iszkb , wmin + (i +1) • szkb>

 

czyli

 

K[0] :  <wmin , wmin + szkb)
K[1] :  <wmin + szk , wmin + 2 • szkb)
...  
K[m - 1] :  <wmin + (m - 1) • szkb, wmax)
K[m] :  <wmax , wmax + szkb)

 

Ponieważ poszczególne kubełki tworzą przedziały prawostronnie otwarte, potrzebujemy ostatniego kubełka K[m] dla wartości maksymalnej wmax, którą mogą osiągać elementy w sortowanym zbiorze. Wynika stąd, iż kubełków będzie m + 1 ponumerowanych kolejno od 0 do m.

Liczba d[j] należy do i-tego kubełka, jeśli spełniona jest nierówność:

 

wmin + i szkb d[j] < wmin + (i - 1) • szkb

 

A stąd otrzymujemy wzór na numer kubełka:

 

i = [  d[j] - wmin ]
szkb

 

Po wyznaczeniu przedziału kubełków, zerujemy kubełki (tzn. tworzymy w nich puste listy elementów). Następnie przeglądamy kolejno wszystkie elementy zbioru, wyznaczamy dla nich odpowiednie kubełki i wstawiamy te elementy to kubełków. Operację wstawiania do kubełka wykonujemy tak, aby wewnątrz kubełka elementy tworzyły listę posortowaną. Jeśli kubełków będzie odpowiednio dużo, to zawierać będą niewiele elementów, zatem operacja tworzenia listy uporządkowanej nie zajmie dużo czasu.

Po wykonaniu przebiegu dystrybucyjnego w poszczególnych kubełkach będziemy posiadali uporządkowane listy elementów. Wykonujemy przebieg zbierający - przeglądamy poszczególne kubełki pobierając z list przechowywane w nich elementy i umieszczając je w zbiorze wynikowym. W efekcie otrzymamy zbiór posortowany.

 

Przykład:

Dla zobrazowania zasady sortowania kubełkowego posortujemy tą metodą poniższy zbiór liczb:

 

{ 23/4  11/4  4/5  41/2  14/5  1/2 }

 

Określamy zakres wartości elementów zbioru:

 

wmin = 1/2
wmax =
41/2

 

Ustalamy liczbę kubełków m = 4.

Wyliczamy szerokość kubełka:

 

szkb =  wmax - wmin  = 41/2 - 1/2  = 1
m 4

 

Wyznaczamy zakresy kolejnych kubełków:

 

K[0] : <1/2, 11/2)
K[1] : <11/2, 21/2)
K[2] : <21/2, 31/2)
K[3] : <31/2, 41/2)
K[4] : <41/2, 51/2)

 

Poszczególne elementy zbioru umieszczamy w kubełkach, których numery wyznaczamy ze wzoru:

 

i = [  element - wmin ]
szkb
23/4 : i = [  23/4 - 1/2 ] = [21/4] = 2
1
11/4 : i = [  11/4 - 1/2 ] = [3/4] = 0
1
4/5 : i = [  4/5 - 1/2 ] = [3/10] = 0
1
41/2 : i = [  41/2 - 1/2 ] = [4] = 4
1
14/5 : i = [  14/5 - 1/2 ] = [13/10] = 1
1
1/2 : i = [  1/2 - 1/2 ] = [0] = 0
1

 

Kubełki mają następującą zawartość:

 

K[0] : <1/2,  11/2)  : 1/2 , 4/5 , 11/4
K[1] : <11/2, 21/2)  : 14/5    
K[2] : <21/2, 31/2)  : 23/4    
K[3] : <31/2, 41/2)  :      
K[4] : <41/2, 51/2)  : 41/2    

 

Pobieramy elementy z kolejnych kubełków i umieszczamy je w zbiorze wynikowym. Zbiór jest posortowany.

 

{ 1/4/ 11/14/23/41/2 }

 

Dodawanie elementu do listy uporządkowanej

Elementy umieszczane w kolejnych kubełkach muszą być posortowane rosnąco. Do sortowania wykorzystamy naturalny w tym przypadku algorytm sortowania przez wstawianie. Dla listy przyjmuje on następującą postać:

 

Dane wejściowe

L[ ] - tablica elementów, z których zbudowana jest lista. Każdy element posiada pole następnik oraz pole dane.
K[ ] - tablica nagłówków list. Elementy K[ ] są liczbami całkowitymi.
ine - indeks nowego elementu w tablicy L[ ], który będzie dodany do listy kubełka, ine ∈ N
ikb - indeks kubełka w tablicy K[ ], do listy którego dodajemy element, ikb ∈ N
we - wartość dodawanego elementu, we ∈ R

Dane wyjściowe

Na liście kubełka K[ikb] zostaje umieszczony nowy element o wartości pola dane równej we. Lista jest posortowana rosnąco

Zmienne pomocnicze

ip - indeks poprzedniego elementu na liście, ip ∈ C
ib - indeks bieżącego elementu na liście, ib ∈ C

 

Lista kroków wstawiania elementu na listę z sortowaniem

K01: L[ine].nastepnik ← 0; L[ine].danewe Inicjujemy nowy element listy
K02: ip ← 0; ib ← K[ikb] Inicjujemy wskaźniki poprzedniego elementu oraz bieżącego
K03: Dopóki (ib > 0) ∧ (L[ib].dane < we) wykonuj
    ipib
    ib ← L[ib].nastepnik
Szukamy miejsca wstawienia nowego elementu na liście skojarzonej z kubełkiem
K04: Jeśli ip = 0, to
    L[ine].nastepnikib;
    K[ikb] ← ine
    idź do K07
Jeśli wskaźnik poprzedniego elementu listy jest równy 0, to pętla z kroku 3 nie wykonała ani jednego obiegu. Dzieje się tak w dwóch przypadkach:
  • lista kubełka jest pusta
  • pierwszy element listy przechowuje dane większe od we

W obu przypadkach nowy element należy wstawić na początek listy. Po tej operacji przechodzimy na koniec algorytmu do kroku 7

K05: Jeśli ib = 0, to
    L[ip].nastepnikine
    Idź do K07
Jeśli wskaźnik bieżącego elementu jest równy 0, to nowy element należy wstawić na koniec listy - za elementem wskazywanym przez wskaźnik ip. Po tej operacji przechodzimy do kroku 7
K06: L[ip].nastepnikine
L[ine].nastepnikib
Jeśli nie wystąpiły dwie poprzednie sytuacje, to pozostaje jedynie wstawienie nowego elementu pomiędzy elementy wskazywane przez ip oraz ib.
K07: ineine + 1
Zakończ
Zwiększamy wskaźnik wolnej pozycji w tablicy elementów list L[ ] i kończymy algorytm.

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów do posortowania;  n N
d[ ] - tablica n-elementowa z elementami rzeczywistymi do posortowania. Indeks pierwszego elementu wynosi 1.
wmin - najmniejszy element w tablicy d[ ];  wmin R
wmax - największy element w tablicy d[ ];  wmax R

Dane wyjściowe

d[ ] - tablica z posortowanymi rosnąco elementami

Zmienne pomocnicze

L[ ] - n-elementowa tablica elementów list. Każdy element posiada całkowite pole następnik oraz rzeczywiste pole dane. Indeksy elementów rozpoczynają się od wartości 1.
K[ ] - tablica (n + 1) elementowa zawierająca nagłówki list kubełków. Każdy element jest liczbą całkowitą. Indeksy elementów rozpoczynają się od wartości 0.
szkb - szerokość przedziału objętego przez kubełek, szkb R
ikb - wyznaczony dla danego elementu numer kubełka, ikb C
ine - indeks wolnej pozycji w tablicy L[ ];   ine N
i,j - zmienne licznikowe pętli;  i,j Î C
we - wartość sortowanego elementu;  we R

 

Lista kroków

K01: Dla i = 0,1,...,n: wykonuj K[i] ← 0
K02:
szkb  wmax - wmin
n
K03: ine ← 1
K04: Dla i = 1,2,...,n: wykonuj K05...K07
K05:     we ← d[i]
K06:
    ikb ← [  we - wmin ]
szkb
K07:     Wstaw wartość we na listę kubełka K[ikb]
K08: j ← 1
K09: Dla ikb = 0,1,...,n: wykonuj K10...K13
K10:     i ← K[ikb]
K11:     Dopóki i > 0: wykonuj K12...K14
K12:         d[j] ← L[i].dane
K13:         jj + 1  
K14:         i ← L[i].nastepnik
K15: Zakończ

 

Schemat blokowy

flow

Pierwszą operacją algorytmu jest wyzerowanie nagłówków list K[ ]. Następnie obliczamy szerokość przedziału kubełka i zapamiętujemy ją w zmiennej szkb.

Elementy list będziemy tworzyli kolejno w tablicy L[ ]. Ustawiamy zmienną ine na pierwszy element tej tablicy. Zmienna ta pełni rolę wskaźnika wolnego elementu w puli L[ ].

Rozpoczynamy pętlę nr 1, której zadaniem jest umieszczenie wszystkich elementów zbioru d[ ] w listach kubełków K[ ]. Element i-ty z d[ ] zapamiętujemy w zmiennej roboczej we (aby zmniejszyć ilość odwołań do tablicy d[ ]). Obliczamy numer kubełka ikb, do którego trafi pobrany element we. Następnie wartość we wstawiamy na listę K[ikb] za pomocą procedury wstawiania elementu na listę uporządkowaną. Pętla nr 1 jest kontynuowana dotąd, aż wszystkie elementy zbioru d[ ] znajdą się na odpowiednich listach kubełków K[ ]. Operacja dystrybucji (rozrzucenia) elementów zostaje zakończona.

Druga faza algorytmu ma za zadanie pozbierać elementy z poszczególnych list uporządkowanych zawartych w kubełkach K[ ].

Zmienna j pełni rolę indeksu wstawianych do d[ ] elementów. Dlatego przyjmuje wartość 1 - początek tablicy d[ ].

Pętla nr 2 wyznacza kolejne kubełki K[ ].

Pętla wewnętrzna nr 3 przegląda elementy listy danego kubełka i zapisuje je do zbioru d[ ].

Po zakończeniu pętli nr 2 w zbiorze d[ ] mamy posortowane elementy. Algorytm jest zakończony.

Programy

Efekt uruchomienia programu
   Sortowanie Kubelkowe II
------------------------------
  (C)2005 mgr Jerzy Walaszek

Przed sortowaniem:

 -508.97  417.11  180.18  457.34  355.41 -813.29  -25.21  189.09 -464.17 -649.78
 -126.22  811.71  244.45  889.28   77.94  286.25  -92.35  596.31   -4.15   28.44
  353.39 -238.40  433.72  589.48   18.92 -198.85  -39.25  809.69 -260.31 -860.96
 -487.18  257.20  683.59 -344.36  297.30 -235.84   -8.61   15.26 -939.39 -126.28

Po sortowaniu:

-939.39 -860.96 -813.29 -649.78 -508.97 -487.18 -464.17 -344.36 -260.31 -238.40
-235.84 -198.85 -126.28 -126.22  -92.35  -39.25  -25.21   -8.61   -4.15   15.26
  18.92   28.44   77.94  180.18  189.09  244.45  257.20  286.25  297.30  353.39
 355.41  417.11  433.72  457.34  589.48  596.31  683.59  809.69  811.71  889.28

 

DevPascal
// Sortowanie kubełkowe - wersja II
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

const
  N    =    40;
  WMIN = -1000.0;
  WMAX =  1000.0;

// Tutaj definiujemy typ elementów listy

type

  TElement = record
    nastepnik : cardinal;
    dane : real;
  end;

// Tutaj deklarujemy zmienne

var
  d : array[1..N] of real;
  L : array[1..N] of TElement;
  K : array[0..N] of integer;
  we,szkb : real;
  ikb,ine,ip,ib,i,j : integer;

begin
  writeln('   Sortowanie Kubelkowe  II   ');
  writeln('------------------------------');
  writeln('  (C)2005 mgr Jerzy Walaszek  ');
  writeln;

// Generujemy zawartość tablicy d[] i wyświetlamy ją

  randomize;
  writeln('Przed sortowaniem:');
  writeln;
  for i := 1 to N do
  begin
    d[i] := WMIN + random() * (WMAX - WMIN);
    write(d[i]:8:2);
  end;
  writeln;

// Zerujemy kubełki

  for i := 0 to N do K[i] := 0;

// Obliczamy szerokość kubełka

  szkb := (WMAX - WMIN) / N;
  ine  := 1;

// Rozrzucamy poszczególne elementy d[i] na listach K[]

  for i := 1 to N do
  begin
    we  := d[i];
    ikb := round((we - WMIN) / szkb);
    L[ine].nastepnik := 0; L[ine].dane := we;
    ip := 0; ib := K[ikb];
    while (ib > 0) and (L[ib].dane < we) do
    begin
      ip := ib; ib := L[ib].nastepnik;
    end;
    if ip = 0 then
    begin
      L[ine].nastepnik := ib; K[ikb] := ine
    end
    else if ib = 0 then
      L[ip].nastepnik := ine
    else
    begin
      L[ip].nastepnik := ine; L[ine].nastepnik := ib;
    end;
    inc(ine);
  end;

// wybieramy dane z kubełków i umieszczamy je w d[]

  j := 1;
  for ikb := 0 to N do
  begin
    i := K[ikb];
    while i > 0 do
    begin
      d[j] := L[i].dane;
      inc(j); i := L[i].nastepnik;
    end;
  end;

// Koniec. Wyświetlamy wyniki

  writeln('Po sortowaniu:');
  writeln;
  for i := 1 to N do write(d[i]:8:2);
  writeln;
  writeln('KONIEC. Nacisnij klawisz Enter...');
  readln;
end.
Code::Blocks
// Sortowanie kubełkowe - wersja II
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int    N    =    40;
const double WMIN = -1000.0;
const double WMAX =  1000.0;

int main()
{
  struct
  {
    unsigned nastepnik;
    double   dane;
  } L[N + 1];

  double d[N],we,szkb;
  int K[N + 1],ikb,ine,ip,ib,i,j;

  cout.precision(2);     // 2 cyfry po przecinku
  cout.setf(ios::fixed); // format stałoprzecinkowy

  cout << "   Sortowanie Kubelkowe  II   \n"
          "------------------------------\n"
          "  (C)2005 mgr Jerzy Walaszek  \n\n"
          "Przed sortowaniem:\n\n";

// Generujemy zawartość tablicy d[] i wyświetlamy ją

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++)
  {
    d[i] = WMIN + (double)rand() / (double)(RAND_MAX+1) * (WMAX - WMIN);
    cout << setw(8) << d[i];
  }
  cout << endl;

// Zerujemy kubełki

  for(i = 0; i <= N; i++) K[i] = 0;

// Obliczamy szerokość kubełka

  szkb = (WMAX - WMIN) / N;
  ine  = 1;

// Rozrzucamy poszczególne elementy d[i] na listach K[]

  for(i = 0; i < N; i++)
  {
    we  = d[i];
    ikb = (int)((we - WMIN) / szkb);
    L[ine].nastepnik = 0; L[ine].dane = we;
    ip = 0; ib = K[ikb];
    while((ib > 0) && (L[ib].dane < we))
    {
      ip = ib; ib = L[ib].nastepnik;
    }
    if(!ip)
    {
      L[ine].nastepnik = ib; K[ikb] = ine;
    }
    else if(!ib) L[ip].nastepnik = ine;
    else
    {
      L[ip].nastepnik = ine; L[ine].nastepnik = ib;
    }
    ine++;
  }

// wybieramy dane z kubełków i umieszczamy je w d[]

  j = 0;
  for(ikb = 0; ikb <= N; ikb++)
  {
    i = K[ikb];
    while(i)
    {
      d[j++] = L[i].dane; i = L[i].nastepnik;
    }
  }

// Koniec. Wyświetlamy wyniki

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(8) << d[i];
  cout << endl;
  return 0;
}
Free Basic
' Sortowanie kubełkowe - wersja II
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

OPTION EXPLICIT

CONST N    =    40
CONST WMIN = -1000
CONST WMAX =  1000

' Tutaj definiujemy typ elementów listy

TYPE TElement
  nastepnik AS UINTEGER
  dane      AS DOUBLE
END TYPE

' Tutaj deklarujemy zmienne

DIM AS DOUBLE d(N),we,szkb
DIM AS TElement L(N)
DIM AS INTEGER K(0 TO N),ikb,ine,ip,ib,i,j

PRINT "   Sortowanie Kubelkowe  II   "
PRINT "------------------------------"
PRINT "  (C)2005 mgr Jerzy Walaszek  "
PRINT

' Generujemy zawartość tablicy d[] i wyświetlamy ją

RANDOMIZE
PRINT "Przed sortowaniem:"
PRINT
FOR i = 1 TO N
  d(i) = WMIN + RND(1) * (WMAX - WMIN)
  PRINT USING "#####.##"; d(i);
NEXT
PRINT

' Zerujemy kubełki

FOR i = 0 TO N: K(i) = 0: NEXT

' Obliczamy szerokość kubełka

szkb = (WMAX - WMIN) / N
ine  = 1

' Rozrzucamy poszczególne elementy d[i] na listach K[]

FOR i = 1 TO N
  we  = d(i)
  ikb = INT((we - WMIN) / szkb)
  L(ine).nastepnik = 0: L(ine).dane = we
  ip = 0: ib = K(ikb)
  WHILE (ib > 0) AND (L(ib).dane < we)
    ip = ib: ib = L(ib).nastepnik
  WEND
  IF ip = 0 THEN
    L(ine).nastepnik = ib: K(ikb) = ine
  ELSEIF ib = 0 THEN
    L(ip).nastepnik = ine
  ELSE
    L(ip).nastepnik = ine: L(ine).nastepnik = ib
  END IF
  ine += 1
NEXT

' wybieramy dane z kubełków i umieszczamy je w d[]

j = 1
FOR ikb = 0 TO N
  i = K(ikb)
  WHILE i > 0
    d(j) = L(i).dane
    j += 1: i = L(i).nastepnik
  WEND
NEXT

' Koniec. Wyświetlamy wyniki

PRINT "Po sortowaniu:"
PRINT
FOR i = 1 TO N: PRINT USING "#####.##"; d(i);: NEXT
PRINT
PRINT "KONIEC. Nacisnij dowolny klawisz..."
SLEEP
END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmbucketsort">
      <h3 style="text-align: center">Sortowanie Kubełkowe II</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie kubełkowe - wersja II
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 40;
var WMIN = -1000;
var WMAX = 1000;
var d = new Array();
var L = new Array();
var K = new Array();
var we,szkb,ikb,ine,ip,ib,i,j,t;

for(i = 1; i <= N; i++) L[i] = new Object();

function main()
{

// Generujemy zawartość tablicy d[] i wyświetlamy ją

  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++)
  {
    d[i] = WMIN + Math.random() * (WMAX - WMIN);
    t += d[i].toFixed(2) + "&nbsp; ";
    if(!((i + 1) % 10)) t += "<BR>";
  }
  t += "<BR>";

// Zerujemy kubełki

  for(i = 0; i <= N; i++) K[i] = 0;

// Obliczamy szerokość kubełka

  szkb = (WMAX - WMIN) / N;
  ine = 1;

// Rozrzucamy poszczególne elementy d[i] na listach K[]

  for(i = 0; i < N; i++)
  {
    we = d[i];
    ikb = Math.floor((we - WMIN) / szkb);
    L[ine].nastepnik = 0; L[ine].dane = we;
    ip = 0; ib = K[ikb];
    while((ib > 0) && (L[ib].dane < we))
    {
      ip = ib; ib = L[ib].nastepnik;
    }
    if(!ip)
    {
      L[ine].nastepnik = ib; K[ikb] = ine;
    }
    else if(!ib) L[ip].nastepnik = ine;
    else
    {
      L[ip].nastepnik = ine; L[ine].nastepnik = ib;
    }
    ine++;
  }

// wybieramy dane z kubełków i umieszczamy je w d[]

  j = 0;
  for(ikb = 0; ikb <= N; ikb++)
  {
    i = K[ikb];
    while(i)
    {
      d[j++] = L[i].dane; i = L[i].nastepnik;
    }
  }

// Koniec. Wyświetlamy wyniki

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++)
  {
    t += d[i].toFixed(2) + "&nbsp; ";
    if(!((i + 1) % 10)) t += "<BR>";
  }
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Sortowanie Kubełkowe II

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badanie algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu sortowania kubełkowego w środowisku opisanym we wstępie. Program testujący jest następujący:

 

DevPascal
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Sortowanie kubełkowe';
  K1    = '-----------------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 8; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  d         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  wmin,wmax : real;                     // zakres elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//-------------------------------------------------------

function Sort : extended;

type
  TElement = record
    nastepnik : cardinal;
    dane : real;
  end;

var
  L : array[1..128000] of TElement;
  K : array[0..128000] of integer;
  we,szkb : real;
  ikb,ine,ip,ib,i,j : integer;

begin
  QueryPerformanceCounter(addr(qpc1));

  for i := 0 to n do K[i] := 0;
  szkb := (wmax - wmin) / n;
  ine  := 1;
  for i := 1 to n do
  begin
    we  := d[i];
    ikb := round((we - wmin) / szkb);
    L[ine].nastepnik := 0; L[ine].dane := we;
    ip := 0; ib := K[ikb];
    while (ib > 0) and (L[ib].dane < we) do
    begin
      ip := ib; ib := L[ib].nastepnik;
    end;
    if ip = 0 then
    begin
      L[ine].nastepnik := ib; K[ikb] := ine
    end
    else if ib = 0 then
      L[ip].nastepnik := ine
    else
    begin
      L[ip].nastepnik := ine; L[ine].nastepnik := ib;
    end;
    inc(ine);
  end;
  j := 1;
  for ikb := 0 to n do
  begin
    i := K[ikb];
    while i > 0 do
    begin
      d[j] := L[i].dane;
      inc(j); i := L[i].nastepnik;
    end;
  end;

  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      wmin := 1; wmax := n;

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0; wmin := 0; wmax := 1;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

 

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):

 

Zawartość pliku wygenerowanego przez program
Nazwa: Sortowanie kubełkowe
-----------------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000144 0.000141 0.000142 0.000142 0.000318
2000 0.000286 0.000286 0.000285 0.000294 0.000922
4000 0.000573 0.000571 0.000577 0.000573 0.002066
8000 0.001121 0.001183 0.001226 0.001230 0.004032
16000 0.002410 0.002389 0.002635 0.002450 0.008189
32000 0,004836 0.004761 0.005129 0.005151 0.017092
64000 0.009612 0.010023 0.010583 0.010323 0.032754
128000 0.019054 0.019218 0.020842 0.021200 0.070825
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Podsumowanie

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania kubełkowego wyciągamy następujące wnioski:

 

Cechy Algorytmu Sortowania Kubełkowego
klasa złożoności obliczeniowej optymistyczna O(n)
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna ?
Sortowanie w miejscu NIE
Stabilność NIE

 

Klasy złożoności obliczeniowej szacujemy następująco:

Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie kubełkowe O(n) O(n) O(n) O(n) O(n)
tpo ≈ tod tpp ≈ tpk
tnp  10 tod
3
  1. Analiza wyników obliczeń w arkuszu kalkulacyjnym pozwala stwierdzić, iż wszystkie czasy sortowania są proporcjonalne do liczby elementów. Zatem algorytm ten posiada liniową klasę złożoności obliczeniowej O(n).
  2. Czas sortowania zbioru nieuporządkowanego jest wyraźnie dłuższy od czasów sortowania zbiorów uporządkowanych.
  3. Algorytm jest mało czuły na niewielkie zaburzenia w zbiorach uporządkowanych.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp
Sortowanie przez scalanie
Sortowanie szybkie
log2n
16
log2n
15
log2n
16
log2n
16
log2n
21
dobrze dobrze dobrze dobrze dobrze
  1. Algorytm sortowania kubełkowego wykazuje logarytmiczny  wzrost prędkości sortowania w stosunku do algorytmu sortowania szybkiego wraz ze wzrostem liczby elementów w sortowanym zbiorze. Musimy jednak sprawiedliwie przyznać, iż w przypadku ogólnym algorytm sortowania szybkiego był szybszy dla maksymalnej, badanej przez nas liczby elementów równej 128000.  Z prostej symulacji wynika, iż algorytm sortowania kubełkowego stanie się szybszy dopiero dla około 4 milionów elementów. Zatem raczej nie stanowi on zagrożenia dla Quick Sort.

Zadania dla ambitnych

  1. Dlaczego zbiory nieuporządkowane są sortowane przez algorytm sortowania kubełkowego dużo wolniej od zbiorów częściowo uporządkowanych?
  2. Uzasadnij, iż algorytm sortowania kubełkowego w podanej postaci nie jest stabilny.
  3. Jak przywrócić stabilność w algorytmie sortowania kubełkowego?

Zobacz również na:

Sortowanie rozrzutowe | Sortowanie kubełkowe 1 | Listy | Sortowanie przez zliczanie | Sortowanie pozycyjne

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.