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

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

' 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

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