Sortowanie kubełkowe
           Bucket Sort


Podrozdziały   Tematy pokrewne

Algorytm

Opisany w tym rozdziale algorytm sortowania kubełkowego pozwala sortować zbiory liczb całkowitych - najlepiej o dużej ilości elementów, lecz o małym zakresie wartości. Zasada działania jest następująca:

  1. Określamy zakres wartości, jakie mogą przyjmować elementy sortowanego zbioru. Niech wmin oznacza najmniejszą wartość, a wmax niech oznacza wartość największą.
  2. Dla każdej możliwej wartości przygotowujemy kubełek-licznik, który będzie zliczał ilość wystąpień tej wartości w sortowanym zbiorze. Liczba liczników jest równa (wmax - wmin + 1). Każdy licznik jest początkowo ustawiony na wartość zero.
  3. Przeglądamy kolejno elementy zbioru od pierwszego do ostatniego. Dla każdego elementu zbioru zwiększamy o jeden zawartość licznika o numerze równym wartości elementu. Na przykład, jeśli kolejny element zbioru ma wartość 3, to zwiększamy licznik o numerze 3. W efekcie po przeglądnięciu wszystkich elementów zbioru liczniki będą zawierały ilość wystąpień każdej z możliwych wartości. Jeśli dany licznik zawiera 0, to wartość równa numerowi licznika w zbiorze nie występuje. Inaczej wartość ta występuje tyle razy, ile wynosi zawartość jej licznika.
  4. Przeglądamy kolejne liczniki zapisując do zbioru wynikowego ich numery tyle razy, ile wynosi ich zawartość. Zbiór wyjściowy będzie posortowany.

Przykład:

Dla przykładu posortujemy opisaną wyżej metodą zbiór { 2 6 4 3 8 7 2 5 7 9 3 5 2 6 }.

Najpierw określamy zakres wartości elementów (w tym celu możemy na przykład wyszukać w zbiorze element najmniejszy i największy). U nas zakres wynosi:

 

wmin = 2,  wmax = 9

 

Potrzebujemy zatem:

 

wmax - wmin + 1 = 9 - 2 + 1 = 8 liczników.

 

Liczniki ponumerujemy zgodnie z wartościami, które będą zliczały:

 

[2] [3] [4] [5] [6] [7] [8] [9]

 

Na początku sortowania wszystkie liczniki mają stan zero:

 

[2:0] [3:0] [4:0] [5:0] [6:0] [7:0] [8:0] [9:0]

 

Teraz przeglądamy kolejne elementy zbioru zliczając ich wystąpienia w odpowiednich licznikach:

 

{ 2 6 4 3 8 7 2 5 7 9 3 5 2 6 }

[2:3] [3:2] [4:1] [5:2] [6:2] [7:2] [8:1] [9:1]

 

Zapis [2:3] oznacza, iż licznik numer 2 zawiera liczbę 3, a to z kolei oznacza, iż liczba 2 pojawiła się w zbiorze 3 razy. Przeglądamy kolejne liczniki począwszy od licznika o najmniejszym numerze (w przypadku sortowania malejącego przeglądanie rozpoczynamy od licznika o największym numerze) i zapisujemy do zbioru wynikowego tyle razy numer licznika, ile wynosi jego zawartość:

 

[2:3] [3:2] [4:1] [5:2] [6:2] [7:2] [8:1] [9:1]

{ 2 2 2 3 3 4 5 5 6 6 7 7 8 9 }

 

Uwaga, pułapka:

Algorytm wymaga ponumerowania liczników kolejno od wmin do wmax. Niektóre języki programowania (np. C++) nie pozwalają numerować dowolnie elementów tablic - zwykle numeracja rozpoczyna się od liczby 0. W takich przypadkach musimy dokonać przeliczenia indeksu licznika, na zliczaną przezeń wartość i na odwrót. Wzory są na szczęście bardzo proste:

Mamy wartość w i chcemy znaleźć indeks licznika, który ją zlicza:

indeks ← w - wmin

Mamy indeks licznika i chcemy znaleźć zliczaną wartość w:

w ← indeks + wmin

 

Specyfikacja problemu

Dane wejściowe

d[ ] - sortowany zbiór liczb całkowitych. Indeksy elementów rozpoczynają się od 1.
n - liczba elementów w zbiorze, n N
wmin - minimalna wartość elementów zbioru,  wmin C
wmax - maksymalna wartość elementów zbioru,  wmax C

Dane wyjściowe

d[ ] - posortowany zbiór liczb całkowitych.

Zmienne pomocnicze

lw[ ] - tablica liczników wartości o indeksach od wmin do wmax. Każdy licznik przechowuje liczbę całkowitą
i, j - zmienne licznikowe pętli, i,j C

 

Lista kroków

K01: Dla i = wmin , wmin + 1,...,wmax: wykonuj lw[i] ← 0
K02: Dla i = 1,2,...,n: wykonuj lw[ d[i] ] ← lw[ d[i] ] + 1
K03: j ← 1
K04: Dla i = wmin , wmin + 1,...,wmax: wykonuj K05
K05:     Dopóki lw[i] > 0 wykonuj:

        d[j] ← i

        lw[i] ← lw[i] - 1

        jj + 1

K06: Zakończ

 

Algorytm ma klasę czasowej złożoności obliczeniowej O(m + n), gdzie m oznacza ilość możliwych wartości, które mogą przyjmować elementy zbioru, a n to ilość sortowanych elementów. Jeśli m jest małe w porównaniu z n (sortujemy dużo elementów o małym zakresie wartości), to na czas sortowania będzie miała wpływ głównie ilość elementów n i klasa złożoności uprości się do postaci O(n). Dzieje się tak dlatego, iż przy równomiernym rozkładzie dużej ilości elementów o małym zakresie wartości liczniki będą równomiernie zapełnione (stan każdego licznika będzie dążył do [n/m]). Zatem algorytm wykona:

  1. m operacji zerowania liczników - czas pomijalnie mały i przy dużym n nie wpływa istotnie na klasę algorytmu.
  2. n operacji zwiększania liczników
  3. n operacji przesłania numerów liczników do zbioru wynikowego - ilość pustych liczników będzie dążyła do zera.

W sytuacji odwrotnej, gdy sortujemy mało elementów o dużym zakresie wartości klasa złożoności zredukuje się z kolei do O(m) - spróbuj uzasadnić ten wynik samemu na podstawie analizy działania poszczególnych fragmentów algorytmu.

 

Schemat blokowy

flow

Algorytm realizujemy w czterech pętlach.

Pętla nr 1 zeruje kolejne liczniki lw[ ].

W pętli nr 2 przeglądamy kolejne elementy zbioru od pierwszego do ostatniego. Dla każdego elementu zwiększamy licznik o numerze równym wartości elementu. Po zakończeniu tej pętli liczniki zawierają liczbę wystąpień poszczególnych wartości elementów w sortowanym zbiorze.

Zmienna j służy do umieszczania w zbiorze wyjściowym kolejnych elementów. Umieszczanie rozpoczniemy od początku zbioru, dlatego zmienne ta przyjmuje wartość 1.

Pętla nr 3 przegląda kolejne liczniki. Jeśli zawartość danego licznika jest większa od zera, to pętla nr 4 umieści w zbiorze wyjściowym odpowiednią ilość numerów licznika, które odpowiadają zliczonym wartościom elementów ze zbioru wejściowego.

Po zakończeniu pętli nr 3 elementy w zbiorze wyjściowym są posortowane. Kończymy algorytm.


 

Programy

Program sortuje 80 liczb z zakresu od -99 do 99.

 

Efekt uruchomienia programu
 Sortowanie kubelkowe
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

 -99  45  96 -41  93  86  52 -30  77 -28 -44 -19  40  65 -28  96  90 -39  52 -49
 -33  35 -31   9 -66   2 -56  62  60 -23  31  47  27 -70  38  85  39  49 -15  12
 -84  60 -46 -58 -49 -47 -50  12 -53   8 -70   2   4  72  42  11  76  84  24  36
  71  71  -2 -27 -19  23 -43 -59  84 -67 -96 -83 -40 -60   6 -10 -30 -78 -76 -48

Po sortowaniu:

 -99 -96 -84 -83 -78 -76 -70 -70 -67 -66 -60 -59 -58 -56 -53 -50 -49 -49 -48 -47
 -46 -44 -43 -41 -40 -39 -33 -31 -30 -30 -28 -28 -27 -23 -19 -19 -15 -10  -2   2
   2   4   6   8   9  11  12  12  23  24  27  31  35  36  38  39  40  42  45  47
  49  52  52  60  60  62  65  71  71  72  76  77  84  84  85  86  90  93  96  96

 

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

program bucketsort;

const WMIN = -99;
const WMAX = 99;
const N = 80;

var
  d   : array[1..N] of integer;
  lw  : array[WMIN..WMAX] of integer;
  i,j : integer;

begin
  writeln(' Sortowanie kubelkowe ');
  writeln('----------------------');
  writeln('(C)2005 Jerzy Walaszek');
  writeln;

// tworzymy zbiór wejściowy do sortowania

  randomize;
  for i := 1 to N do d[i] := WMIN + random(WMAX - WMIN + 1);

// wyświetlamy zawartość zbioru przed sortowaniem

  writeln('Przed sortowaniem:');
  writeln;
  for i := 1 to N do write(d[i]:4);
  writeln;

// sortujemy

// najpierw zerujemy liczniki

  for i := WMIN to WMAX do lw[i] := 0;

// zliczamy w odpowiednich licznikach wystąpienia
// wartości elementów sortowanego zbioru

  for i := 1 to N do inc(lw[d[i]]);

// zapisujemy do zbioru wynikowego numery niezerowych liczników
// tyle razy, ile wynosi ich zawartość

  j := 1;
  for i := WMIN to WMAX do
    while lw[i] > 0 do
    begin
      d[j] := i; inc(j); dec(lw[i]);
    end;

// wyświetlamy zawartość zbioru po sortowaniu

  writeln('Po sortowaniu:');
  writeln;
  for i := 1 to N do write(d[i]:4);

// koniec

  writeln;
  writeln('Gotowe. Nacisnij klawisz ENTER...');
  readln;
end.
Code::Blocks
// Sortowanie Kubełkowe
//--------------------------------------------------------
// (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;

int main()
{
  const int WMIN = -99;
  const int WMAX = 99;
  const int N = 80;
  int d[N],lw[WMAX - WMIN + 1],i,j;

  cout << " Sortowanie kubelkowe \n"
          "----------------------\n"
          "(C)2005 Jerzy Walaszek\n\n";

// tworzymy zbiór wejściowy do sortowania

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++) d[i] = WMIN + rand() % (WMAX - WMIN + 1);

// wyświetlamy zawartość zbioru przed sortowaniem

  cout << "Przed sortowaniem:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;

// sortujemy

// najpierw zerujemy liczniki

  for(i = WMIN; i <= WMAX; i++) lw[i - WMIN] = 0;

// zliczamy w odpowiednich licznikach wystąpienia
// wartości elementów sortowanego zbioru

  for(i = 0; i < N; i++) lw[d[i] - WMIN]++;

// zapisujemy do zbioru wynikowego numery niezerowych liczników
// tyle razy, ile wynosi ich zawartość

  j = 0;
  for(i = WMIN; i <= WMAX; i++) while(lw[i - WMIN]--) d[j++] = i;

// wyświetlamy zawartość zbioru po sortowaniu

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];

// koniec

  cout << endl;
  return 0;
}
Free Basic
' Sortowanie Kubełkowe
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

CONST WMIN = -99
CONST WMAX =  99
CONST N    =  80

DIM AS INTEGER d(N),lw(WMIN TO WMAX),i,j

PRINT " Sortowanie kubelkowe "
PRINT "----------------------"
PRINT "(C)2005 Jerzy Walaszek"
PRINT

' tworzymy zbiór wejściowy do sortowania

RANDOMIZE
FOR i = 1 TO N: d(i) = WMIN + INT(RND(1) * (WMAX - WMIN + 1)): NEXT

' wyświetlamy zawartość zbioru przed sortowaniem

PRINT "Przed sortowaniem:"
PRINT
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT

' sortujemy

' najpierw zerujemy liczniki

FOR i = WMIN TO WMAX: lw(i) = 0: NEXT

' zliczamy w odpowiednich licznikach wystąpienia
' wartości elementów sortowanego zbioru

FOR i = 1 TO N: lw(d(i)) += 1: NEXT

' zapisujemy do zbioru wynikowego numery niezerowych liczników
' tyle razy, ile wynosi ich zawartość

j = 1
FOR i = WMIN TO WMAX
  WHILE lw(i) > 0
    d(j) = i: j += 1: lw(i) -= 1
  WEND
NEXT

' wyświetlamy zawartość zbioru po sortowaniu

PRINT "Po sortowaniu:"
PRINT
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

' koniec

PRINT
PRINT "Gotowe. 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</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
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

function main()
{
  var WMIN = -99;
  var WMAX =  99;
  var N    =  80;
  var d    = new Array(N);
  var lw   = new Array(WMAX - WMIN + 1);
  var i,j,t;

// tworzymy zbiór wejściowy do sortowania

  for(i = 0; i < N; i++)
    d[i] = WMIN + Math.floor(Math.random() * (WMAX - WMIN + 1));

// wyświetlamy zawartość zbioru przed sortowaniem

  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++)
    if((i + 1) % 20) t += d[i] + " "; else t += d[i] + "<BR>";
  t += "<BR>";

// sortujemy

// najpierw zerujemy liczniki

  for(i = WMIN; i <= WMAX; i++) lw[i - WMIN] = 0;

// zliczamy w odpowiednich licznikach wystąpienia
// wartości elementów sortowanego zbioru

  for(i = 0; i < N; i++) lw[d[i] - WMIN]++;

// zapisujemy do zbioru wynikowego numery niezerowych liczników
// tyle razy, ile wynosi ich zawartość

  j = 0;
  for(i = WMIN; i <= WMAX; i++) while(lw[i - WMIN]--) d[j++] = i;

// wyświetlamy zawartość zbioru po sortowaniu

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++)
    if((i + 1) % 20) t += d[i] + " "; else t += d[i] + "<BR>";

// koniec

  document.getElementById("t_out").innerHTML = t;
} 

</script> 

  </body>
</html>

 

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

Sortowanie Kubełkowe

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


...

 


Zobacz również na:

Sortowanie rozrzutowe | Listy | Sortowanie kubełkowe 2 | 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.