Algorytmy Sortujące - Sortowanie kubełkowe

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 w_min oznacza dolny kres wartości elementów d[ ], a w_max niech oznacza kres górny. Wartości te tworzą przedział liczbowy <w_min, w_max>, 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:

Poszczególne kubełki to:

dla i = 0,1,...,m: [w_min + i • sz_kb , w_min + (i +1) • sz_kb]

czyli

K[0] :	<w_min , w_min + sz_kb)
K[1] :	<w_min + sz_k , w_min + 2 • sz_kb)
...
K[m - 1] :	<w_min + (m - 1) • sz_kb, w_max)
K[m] :	<w_max , w_max + sz_kb)

Ponieważ poszczególne kubełki tworzą przedziały prawostronnie otwarte, potrzebujemy ostatniego kubełka K[m] dla wartości maksymalnej w_max, 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ść:

w_min + i • sz_kb

d[j] < w_min + (i - 1) • sz_kb

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

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:

{ 2³/₄ 1¹/₄ ⁴/₅ 4¹/₂ 1⁴/₅ ¹/₂ }

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

w_min = ¹/₂
w_max = 4¹/₂

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

Wyliczamy szerokość kubełka:

Wyznaczamy zakresy kolejnych kubełków:

K[0] : <¹/₂, 1¹/₂)
K[1] : <1¹/₂, 2¹/₂)
K[2] : <2¹/₂, 3¹/₂)
K[3] : <3¹/₂, 4¹/₂)
K[4] : <4¹/₂, 5¹/₂)

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

2³/₄ : i = [	2³/₄ - ¹/₂	] = [2¹/₄] = 2
	1
1¹/₄ : i = [	1¹/₄ - ¹/₂	] = [³/₄] = 0
	1
⁴/₅ : i = [	⁴/₅ - ¹/₂	] = [³/₁₀] = 0
	1
4¹/₂ : i = [	4¹/₂ - ¹/₂	] = [4] = 4
	1
1⁴/₅ : i = [	1⁴/₅ - ¹/₂	] = [1³/₁₀] = 1
	1
¹/₂ : i = [	¹/₂ - ¹/₂	] = [0] = 0
	1

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

K[0] :	[¹/₂, 1¹/₂)	:	¹/₂	, ⁴/₅	, 1¹/₄
K[1] :	[1¹/₂, 2¹/₂)	:	1⁴/₅
K[2] :	[2¹/₂, 3¹/₂)	:	2³/₄
K[3] :	[3¹/₂, 4¹/₂)	:
K[4] :	[4¹/₂, 5¹/₂)	:	4¹/₂

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

{ ¹/₂⁴/₅1¹/₄1⁴/₅2³/₄4¹/₂ }

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.
i_ne	- indeks nowego elementu w tablicy L[ ], który będzie dodany do listy kubełka, i_ne ∈ N
i_kb	- indeks kubełka w tablicy K[ ], do listy którego dodajemy element, i_kb ∈ N
w_e	- wartość dodawanego elementu, w_e ∈ R

Dane wyjściowe

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

Zmienne pomocnicze

i_p	- indeks poprzedniego elementu na liście, i_p ∈ C
i_b	- indeks bieżącego elementu na liście, i_b ∈ C

Lista kroków wstawiania elementu na listę z sortowaniem

K01:	L[i_ne].następnik ← 0; L[i_ne].dane ← w_e	Inicjujemy nowy element listy
K02:	i_p ← 0; i_b ← K[i_kb]	Inicjujemy wskaźniki poprzedniego elementu oraz bieżącego
K03:	Dopóki (i_b > 0) ∧ (L[i_b].dane < w_e) wykonuj: i_p ← i_b i_b ← L[i_b].następnik	Szukamy miejsca wstawienia nowego elementu na liście skojarzonej z kubełkiem
K04:	Jeśli i_p = 0, to: L[i_ne].następnik ← i_b; K[i_kb] ← i_ne idź do kroku 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 w_e 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 i_b = 0, to: L[i_p].następnik ← i_ne Idź do kroku 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 i_p. Po tej operacji przechodzimy do kroku 7
K06:	L[i_p].następnik ← i_ne L[i_ne].następnik ← i_b	Jeśli nie wystąpiły dwie poprzednie sytuacje, to pozostaje jedynie wstawienie nowego elementu pomiędzy elementy wskazywane przez i_p oraz i_b.
K07:	i_ne ← i_ne + 1 Zakończ	Zwiększamy wskaźnik wolnej pozycji w tablicy elementów list L[ ] i kończymy algorytm.

do podrozdziału do strony

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.
w_min	- najmniejszy element w tablicy d[ ]; w_min ∈ R
w_max	- największy element w tablicy d[ ]; w_max ∈ 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.
sz_kb	-	szerokość przedziału objętego przez kubełek, sz_kb ∈ R
i_kb	-	wyznaczony dla danego elementu numer kubełka, i_kb ∈ C
i_ne	-	indeks wolnej pozycji w tablicy L[ ]; i_ne ∈ N
i,j	-	zmienne licznikowe pętli; i,j Î C
w_e	-	wartość sortowanego elementu; w_e ∈ R

Lista kroków

K01:	Dla i = 0,1,...,n: wykonuj: K[i] ← 0
K02:
K03:	i_ne ← 1
K04:	Dla i = 1,2,...,n: wykonuj kroki K05...K07
K05:	w_e ← d[i]
K06:
K07:	Wstaw wartość w_e na listę kubełka K[i_kb]
K08:	j ← 1
K09:	Dla i_kb = 0,1,...,n: wykonuj kroki K10...K13
K10:	i ← K[i_kb]
K11:	Dopóki i > 0: wykonuj kroki K12...K14
K12:	d[j] ← L[i].dane
K13:	j ← j + 1
K14:	i ← L[i].następnik
K15:	Zakończ

Schemat blokowy

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

Elementy list będziemy tworzyli kolejno w tablicy L[ ]. Ustawiamy zmienną i_ne 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 w_e (aby zmniejszyć ilość odwołań do tablicy d[ ]). Obliczamy numer kubełka i_kb, do którego trafi pobrany element w_e. Następnie wartość w_e wstawiamy na listę K[i_kb] 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.

do podrozdziału do strony

C++

// Sortowanie kubełkowe 2
//-----------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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;

  // 2 cyfry po przecinku
  cout.precision(2);

  // format stałoprzecinkowy
  cout.setf(ios::fixed);

  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 << 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 << endl;
  system("pause");
  return 0;
}

Pascal

// Sortowanie kubełkowe 2
//-----------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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;
  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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

' Sortowanie kubełkowe 2
'-----------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

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
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
PRINT "Nacisnij dowolny klawisz..."
SLEEP
END

Python (dodatek)

# Sortowanie kubełkowe 2
#-----------------------
# (C)2012 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

n    =    40
wmin = -999.0
wmax =  999.0

class List:
    def __init__(self):
        self.nastepnik = 0
        self.dane = 0.0

l = [List() for _ in range(n + 1)]
d = [0.0] * n
k = [0] * (n + 1)

print(" Sortowanie Kubełkowe  II")
print("--------------------------")
print("(C)2026 mgr Jerzy Wałaszek")
print()
print("Przed sortowaniem:")
print()

# Generujemy zawartość tablicy d[]
# i wyświetlamy ją
for i in range(n):
    d[i] = random.uniform(wmin,wmax)
    print("%8.2f" % d[i], end="")
print()
print()

# Obliczamy szerokość kubełka
szkb = (wmax - wmin) / n
ine  = 1

# Rozrzucamy poszczególne
# elementy d[i] na listach K[]
for i in range(n):
    we  = d[i]
    ikb = int((we - wmin) / szkb)
    l[ine].nastepnik = 0
    l[ine].dane = we
    ip = 0
    ib = k[ikb]
    while ib and l[ib].dane < we:
        ip = ib
        ib = l[ib].nastepnik
    if not ip:
        l[ine].nastepnik = ib
        k[ikb] = ine
    elif not ib:
        l[ip].nastepnik = ine
    else:
        l[ip].nastepnik = ine
        l[ine].nastepnik = ib
    ine += 1

# wybieramy dane z kubełków
# i umieszczamy je w d[]
j = 0
for ikb in range(n + 1):
    i = k[ikb]
    while i:
        d[j] = l[i].dane
        j += 1
        i = l[i].nastepnik

# Koniec. Wyświetlamy wyniki
print("Po sortowaniu:")
print()
for i in range(n):
    print("%8.2f" % d[i], end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

 Sortowanie Kubełkowe  II
--------------------------
(C)2026 mgr Jerzy Wałaszek

Przed sortowaniem:

  102.41 -165.06  507.17   -9.04  -42.09  167.02 -564.50 -673.01  321.34 -641.40
 -303.40  337.81 -918.70 -235.13  294.05  203.94 -846.23   60.33  206.31 -698.58
  571.51 -744.34 -213.95  256.22  380.58  474.06 -205.19 -806.32  655.63 -358.31
 -719.41    2.28  854.49 -548.88  505.31  566.92  163.62 -639.59 -706.80  866.58

Po sortowaniu:

 -918.70 -846.23 -806.32 -744.34 -719.41 -706.80 -698.58 -673.01 -641.40 -639.59
 -564.50 -548.88 -358.31 -303.40 -235.13 -213.95 -205.19 -165.06  -42.09   -9.04
    2.28   60.33  102.41  163.62  167.02  203.94  206.31  256.22  294.05  321.34
  337.81  380.58  474.06  505.31  507.17  566.92  571.51  655.63  854.49  866.58

Naciśnij Enter...

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>

do podrozdziału do strony

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

do podrozdziału do strony

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

do podrozdziału do 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 2
Bucket Sort 2

Algorytm

Dodawanie elementu do listy uporządkowanej

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków wstawiania elementu na listę z sortowaniem

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Kubełkowe II

Podsumowanie

Zadania dla ambitnych

Sortowanie kubełkowe 2Bucket Sort 2

Algorytm

Dodawanie elementu do listy uporządkowanej

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków wstawiania elementu na listę z sortowaniem

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Kubełkowe II

Podsumowanie

Zadania dla ambitnych

Sortowanie kubełkowe 2
Bucket Sort 2