Algorytmy Sortujące - Sortowanie kubełkowe

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:

Określamy zakres wartości, jakie mogą przyjmować elementy sortowanego zbioru. Niech w_min oznacza najmniejszą wartość, a w_max niech oznacza wartość największą.
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 (w_max - w_min + 1). Każdy licznik jest początkowo ustawiony na wartość zero.
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.
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:

w_min = 2, w_max = 9

Potrzebujemy zatem:

w_max - w_min + 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 w_min do w_max. 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:

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

Algorytm ma klasę złożoności obliczeniowej O(m + n), gdzie n oznacza liczbę elementów, a m oznacza liczbę ich wartości.

Na początek: podrozdziału strony

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
w_min	- minimalna wartość elementów zbioru, w_min ∈ C
w_max	- maksymalna wartość elementów zbioru, w_max ∈ C

Dane wyjściowe

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

Zmienne pomocnicze

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

Lista kroków

K01:	Dla i = w_min , w_min + 1,...,w_max: wykonuj: l_w[i] ← 0
K02:	Dla i = 1,2,...,n: wykonuj: l_w[ d[i] ] ← l_w[ d[i] ] + 1
K03:	j ← 1
K04:	Dla i = w_min , w_min + 1,...,w_max: wykonuj krok K05
K05:	Dopóki l_w[i] > 0: wykonuj: d[j] ← i l_w[i] ← l_w[i] - 1 j ← j + 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 [ⁿ/_m]). Zatem algorytm wykona:

m operacji zerowania liczników - czas pomijalnie mały i przy dużym n nie wpływa istotnie na klasę algorytmu.
n operacji zwiększania liczników
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

obrazek

Algorytm realizujemy w czterech pętlach.

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

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.

Na początek: podrozdziału strony

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

C++

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

Pascal

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

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>

Wynik:

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

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 kubełkowe
Bucket Sort

Algorytm

Uwaga, pułapka:

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

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

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Kubełkowe

Sortowanie kubełkowe Bucket Sort

Algorytm

Uwaga, pułapka:

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

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

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Kubełkowe

Sortowanie kubełkowe
Bucket Sort