Sortowanie rozrzutowe
           Distribution Sort


Podrozdziały   Tematy pokrewne
 

Algorytm

Wszystkie opisane dotychczas algorytmy sortujące opierają się na sprawdzaniu uporządkowania zbioru, które polega na porównywaniu elementów. Udowodniono, iż barierą efektywności takich algorytmów w przypadku ogólnym (sortowanie zbioru o losowym rozkładzie elementów) jest klasa złożoności obliczeniowej O(n log n). Zachodzi zatem naturalne pytanie: czy istnieją inne sposoby sortowania o niższej klasie złożoności obliczeniowej?

Na samym początku III części "Sztuki Programowania Komputerów" prof. Donald Knuth opisuje znany od dawna sposób porządkowania talii kart.

Ustalmy kolejność kolorów kart wg ich starszeństwa (pierwszy pik, ostatni trefl):

 

- pik
- kier
- karo
- trefl

 

Teraz ustalmy kolejność figur (dla uproszczenia przyjmujemy talię z 24 kart, chociaż algorytm jest również poprawny dla pełnej talii 52 kart):

 

A - as
K - król
D - dama
W - walet
T - dziesiątka
9 - dziewiątka

 

Przykład:

Załóżmy, iż mamy potasowaną losowo talię 24 kart:

 

D K K 9 D W A K 9 T A K T W A D D W 9 A 9 W T T

 

Chcemy je posortować szybko tak, aby najpierw występowały piki, później kiery, kara a na końcu trefle. W obrębie każdego koloru karty powinny być uporządkowane wg podanej powyżej kolejności. Postępujemy tak:

Najpierw kolejne karty układamy na 6 stosów wg figur (kolorem się chwilowo nie przejmujemy):

 

A   K   D   W   T   9
A K D W T 9
A K D W T 9
A K D W T 9
A K D W T 9

 

Poszczególne stosy łączymy ze sobą w talie kart - karty pobieramy z kupek w tej samej kolejności, w której były na nie wstawiane (u nas wstawianie rozpoczęliśmy od góry, zatem również od góry rozbieramy każdą z kupek):

 

A A A A K K K K D D D D W W W W T T T T 9 9 9 9

 

W drugim kroku otrzymaną talie rozkładamy na 4 stosy wg kolorów:

 

     
A A A A
K K K K
D D D D
W W W W
T T T T
9 9 9 9

 

Teraz wystarczy połączyć ze sobą otrzymane stosy w jedną talię 24 kart:

 

A K D W T 9 A K D W T 9 A K D W T 9 A K D W T 9

 

Talia kart jest posortowana.

 

Lista kroków

K01: Przygotuj miejsce na tyle stosów, ile figur mogą mieć karty. Pierwszy stos będzie dla najstarszej karty, a ostatni dla najmłodszej.
K02: Rozdziel poszczególne karty na przygotowane wcześniej stosy wg figur - np. wszystkie asy idą do stosu asów, króle idą do stosu króli, itd.
K03: Złóż ze sobą karty w kolejnych stosach poczynając od stosu zawierającego najstarsze figury, a kończąc na stosie z najmłodszymi figurami.
K04: Przygotuj miejsce dla czterech stosów kolorów. Stosy powinny być ułożone w kolejności starszeństwa kolorów, np. piki, kiery, karo, trefle.
K05: Rozdziel karty na poszczególne stosy wg ich kolorów.
K06: Złóż ze sobą karty z kolejnych stosów poczynając od stosu zawierającego karty w najstarszym kolorze a kończąc na stosie z kartami w najmłodszym kolorze. Talia zostanie uporządkowana
K07: Zakończ algorytm

 

Zwróć uwagę, iż przedstawiona metoda w ogóle nie porównuje elementów ze sobą. Elementy trafiają do odpowiednich stosów (są rozrzucane - stąd nazwa sortowanie rozrzutowe) na podstawie swojej wartości, a nie na podstawie ich relacji z innymi elementami zbioru. Dzięki takiemu podejściu zmieniona zostaje klasa czasowej złożoności obliczeniowej:

 

Pierwsza operacja - rozłożenie n elementów na m kupek ma klasę złożoności O(n).

Druga operacja - złączenie m kupek w n elementów ma klasę złożoności O(m).

 

Sumarycznie cały algorytm będzie posiadał klasę złożoności O(n + m). Jest to klasa liniowa, zatem sortowanie będzie bardzo szybkie. Co więcej, algorytm tego typu nie posiada przypadku pesymistycznego - czas sortowania każdego zbioru danych jest porównywalny. Mankament tego rozwiązania stanowi dodatkowe zapotrzebowanie na pamięć O(n) - musimy zarezerwować komórki na elementy przechowywane w stosach.

Programy

W programach wykorzystuje się opisany algorytm sortowania kart, który może stanowić część większego programu gry w karty (to już pozostawiamy inwencji czytelnika). Od razu zastrzegam, iż problem sortowania kart rozwiązuje się o wiele prościej, jednakże tutaj chodzi o przedstawienie sposobu realizacji opisanego algorytmu. Zatem program ma raczej wartość dydaktyczną niż użytkową.

 

Efekt uruchomienia programu
              ♠ KD987
              ♥ D83
              ♦ D54
              ♣ K3

♠ A3                         ♠ 652
♥ KW4                        ♥ T96
♦ W973                       ♦ A86
♣ D764                       ♣ W852

              ♠ WT4
              ♥ A752
              ♦ KT2
              ♣ AT9

 

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

program skart;

uses Crt;

// Definicje typów danych
//--------------------------------------------------------

type

  TKolor = (K_PIK,K_KIER,K_KARO,K_TREFL,K_PUSTY);
  TFigura = (F_A,F_K,F_D,F_W,F_10,F_9,F_8,F_7,F_6,F_5,F_4,F_3,F_2,F_0);
  TKarta = record
    Kolor : TKolor;
    Figura : TFigura;
  end;

// Definicje zmiennych globalnych
//--------------------------------------------------------

var
  talia : array[1..52] of TKarta;
  gracz : array[1..4,1..13] of TKarta;

// Definicje procedur i funkcji
//--------------------------------------------------------

// Procedura inicjuje talię kart
//--------------------------------------------------------
procedure Inicjuj_talie;
var
  i : integer;
  k : TKolor;
  f : TFigura;
begin
  k := K_PIK; f := F_A;
  for i := 1 to 52 do
  begin
    talia[i].Kolor := k; talia[i].Figura := f;
    inc(f);
    if f = F_0 then
    begin
      inc(k); f := F_A;
    end
  end;
end;

// Procedura tasuje talię kart
//--------------------------------------------------------
procedure Tasuj_talie;
var
  i,a,b : integer;
  x     : TKarta;
begin
  for i := 1 to 1000 do
  begin
    a := 1 + random(52); b := 1 + random(52);
    x := talia[a]; talia[a] := talia[b]; talia[b] := x;
  end;
end;

// Procedura rozdaje karty poszczególnym graczom
//--------------------------------------------------------
procedure Rozdaj_karty;
var
  i,j,k : integer;
begin
  k := 1;
  for i := 1 to 4 do
    for j := 1 to 13 do
    begin
      gracz[i,j] := talia[k];
      inc(k);
    end;
end;

// Procedura sortuje karty gracza wg kolorów i figur
//--------------------------------------------------------
procedure Sortuj_karty(g : integer);
var
  karty   : array[0..3,0..12] of TKarta;
  lfig    : array[TFigura] of integer;
  lkol    : array[TKolor] of integer;
  f   : TFigura;
  k   : TKolor;
  i,j : integer;
begin

// Ustawiamy liczniki figur

  for f := F_A to F_2 do lfig[f] := 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// figur wg figury

  for i := 1 to 13 do
  begin
     f := gracz[g,i].Figura;
     karty[lfig[f],ord(f)] := gracz[g,i];
     inc(lfig[f]);
  end;

// Przeglądamy tablicę figur pobierając z niej karty do ręki gracza

  i := 1;
  for f := F_A to F_2 do
    for j := 0 to lfig[f] - 1 do
    begin
      gracz[g,i] := karty[j,ord(f)];
      inc(i);
    end;

// Ustawiamy liczniki kolorów

  for k := K_PIK to K_TREFL do lkol[k] := 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// kolorów wg koloru karty

  for i := 1 to 13 do
  begin
     k := gracz[g,i].Kolor;
     karty[ord(k),lkol[k]] := gracz[g,i];
     inc(lkol[k]);
  end;

// Przeglądamy tablicę kolorów pobierając z niej karty do ręki gracza

  i := 1;
  for k := K_PIK to K_TREFL do
    for j := 0 to lkol[k] - 1 do
    begin
      gracz[g,i] := karty[ord(k),j];
      inc(i);
    end;
end;

// Procedura wyświetla karty gracza wg jego numeru:
// 1 : gracz u góry    (15,1)
// 2 : gracz po prawej (30,6)
// 3 : gracz u dołu    (15,11)
// 4 : gracz po lewej  (1,6)
// okna konsoli. Wydruk zajmuje 4 wiersze, w każdym do 15 znaków.
// Figurę 10 wyświetlamy jako T - każda karta powinna zajmować jeden
// znak, a zapis 10 wymaga dwóch znaków.
//--------------------------------------------------------
procedure Wyswietl_karty(g : integer);
const
  kolory  : string[4]  = (#6#3#4#5);
  figury  : string[13] = ('AKDWT98765432');
  px      : array[1..4] of integer = (15,30,15,1);
  py      : array[1..4] of integer = (1,6,11,6);
var
  i : integer;
  k : TKolor;
begin
  for k := K_PIK to K_TREFL do
  begin
    gotoXY(px[g], py[g] + ord(k));
    write(kolory[1 + ord(k)],' ');
    for i := 1 to 13 do
      if gracz[g,i].Kolor = k then
        write(figury[1 + ord(gracz[g,i].Figura)]);
  end;
end;

//---------------
// Program główny
//---------------

var
  i : integer;
begin
  Randomize;
  Inicjuj_talie;
  Tasuj_talie;
  Rozdaj_karty;
  for i := 1 to 4 do
  begin
    Sortuj_karty(i);
    Wyswietl_karty(i);
  end;
  gotoXY(1,16); writeln('Gotowe. Nacisnij klawisz Enter...');
  readln;
end.
Code::Blocks
// Sortowanie Kart
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

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

using namespace std;

// Definicje typów danych
//--------------------------------------------------------

  enum TKolor {K_PIK,K_KIER,K_KARO,K_TREFL,K_PUSTY};
  enum TFigura {F_A,F_K,F_D,F_W,F_10,F_9,F_8,F_7,F_6,F_5,F_4,F_3,F_2,F_0};
  struct TKarta
  {
    TKolor  Kolor;
    TFigura Figura;
  };
  

// Definicja operatora ++ dla typów TKolor i TFigura
//---------------------------------------------------------
inline TKolor operator++(TKolor &rs,int)
{
    return rs = (TKolor)(rs + 1);
}

inline TFigura operator++(TFigura &rs,int)
{
    return rs = (TFigura)(rs + 1);
}

// Deklaracje zmiennych globalnych
//--------------------------------------------------------

  TKarta talia[52];
  TKarta gracz[4][13];

// Definicje procedur i funkcji
//--------------------------------------------------------

// Procedura ustawia pozycję wydruku w oknie konsoli
//--------------------------------------------------------
void gotoXY(int x, int y)
{
  COORD p;
  HANDLE h;

  h = GetStdHandle(STD_OUTPUT_HANDLE);
  p.X = x - 1; p.Y = y - 1;
  SetConsoleCursorPosition(h,p);
}

// Procedura inicjuje talię kart
//--------------------------------------------------------
void Inicjuj_talie()
{
  int i;
  TKolor k;
  TFigura f;

  k = K_PIK; f = F_A;
  for(i = 0; i < 52; i++)
  {
    talia[i].Kolor = k; talia[i].Figura = f;
    f++;
    if(f == F_0)
    {
      k++; f = F_A;
    }
  }
}

// Procedura tasuje talię kart
//--------------------------------------------------------
void Tasuj_talie()
{
  int i,a,b;

  for(i = 0; i < 1000; i++)
  {
    a = rand() % 52; b = rand() % 52;
    swap(talia[a], talia[b]);
  }
}

// Procedura rozdaje karty poszczególnym graczom
//--------------------------------------------------------
void Rozdaj_karty()
{
  int i,j,k;

  k = 0;
  for(i = 0; i < 4; i++)
    for(j = 0; j < 13; j++) gracz[i][j] = talia[k++];
}

// Procedura sortuje karty gracza wg kolorów i figur
//--------------------------------------------------------
void Sortuj_karty(int g)
{
  TKarta karty[4][13];
  int lfig[13], lkol[4],i,j;
  TFigura f;
  TKolor  k;

// Ustawiamy liczniki figur

  for(f = F_A; f < F_0; f++) lfig[f] = 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// figur wg figury

  for(i = 0; i < 13; i++)
  {
     f = gracz[g][i].Figura;
     karty[lfig[f]++][f] = gracz[g][i];
  }

// Przeglądamy tablicę figur pobierając z niej karty do ręki gracza

  i = 0;
  for(f = F_A; f < F_0; f++)
    for(j = 0; j < lfig[f]; j++) gracz[g][i++] = karty[j][f];

// Ustawiamy liczniki kolorów

  for(k = K_PIK; k < K_PUSTY; k++) lkol[k] = 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// kolorów wg koloru karty

  for(i = 0; i < 13; i++)
  {
     k = gracz[g][i].Kolor;
     karty[k][lkol[k]++] = gracz[g][i];
  }

// Przeglądamy tablicę kolorów pobierając z niej karty do ręki gracza

  i = 0;
  for(k = K_PIK; k < K_PUSTY; k++)
    for(j = 0; j < lkol[k]; j++) gracz[g][i++] = karty[k][j];
}

// Procedura wyświetla karty gracza wg jego numeru:
// 1 : gracz u góry    (15,1)
// 2 : gracz po prawej (30,6)
// 3 : gracz u dołu    (15,11)
// 4 : gracz po lewej  (1,6)
// okna konsoli. Wydruk zajmuje 4 wiersze, w każdym do 15 znaków.
// Figurę 10 wyświetlamy jako T - każda karta powinna zajmować jeden
// znak, a zapis 10 wymaga dwóch znaków.
//--------------------------------------------------------
void Wyswietl_karty(int g)
{
  const char kolory[4]  = {6,3,4,5};
  const char * figury = "AKDWT98765432";
  const int px[4] = {15,30,15,1};
  const int py[4] = {1,6,11,6};

  int i;
  TKolor k;

  for(k = K_PIK; k < K_PUSTY; k++)
  {
    gotoXY(px[g],py[g] + k);
    cout << kolory[k] << " ";
    for(i = 0; i < 13; i++)
      if(gracz[g][i].Kolor == k) cout << figury[gracz[g][i].Figura];
  }
}

//---------------
// Program główny
//---------------

int main()
{
  int i;

  srand((unsigned)time(NULL));

  Inicjuj_talie();
  Tasuj_talie();
  Rozdaj_karty();
  for(i = 0; i < 4; i++)
  {
    Sortuj_karty(i); Wyswietl_karty(i);
  }
  gotoXY(1,16);

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

' Definicje typów danych
'--------------------------------------------------------

OPTION EXPLICIT

ENUM TKolor
     K_PIK
     K_KIER
     K_KARO
     K_TREFL
     K_PUSTY
END ENUM

ENUM TFigura
     F_A
     F_K
     F_D
     F_W
     F_10
     F_9
     F_8
     F_7
     F_6
     F_5
     F_4
     F_3
     F_2
     F_0
END ENUM

TYPE TKarta
  Kolor  AS TKolor
  Figura AS TFigura
END TYPE

' Definicje zmiennych globalnych
'--------------------------------------------------------

DIM SHARED talia(52) AS TKarta
DIM SHARED gracz(4,13) AS TKarta

' Definicje procedur i funkcji
'--------------------------------------------------------

' Procedura inicjuje talię kart
'--------------------------------------------------------

DECLARE SUB Inicjuj_talie()

SUB Inicjuj_talie()

  DIM i AS INTEGER
  DIM k AS TKolor
  DIM f AS TFigura

  k = K_PIK: f = F_A
  FOR i = 1 TO 52
    talia(i).Kolor = k: talia(i).Figura = f
    f += 1
    IF f = F_0 THEN
      k += 1: f = F_A
    END IF
  NEXT
END SUB

' Procedura tasuje talię kart
'--------------------------------------------------------

DECLARE SUB Tasuj_talie()

SUB Tasuj_talie()

  DIM AS INTEGER i,a,b

  FOR i = 1 TO 1000
    a = 1 + INT(RND(1) * 52): b = 1 + INT(RND(1) * 52)
    SWAP talia(a), talia(b)
  NEXT
END SUB

' Procedura rozdaje karty poszczególnym graczom
'--------------------------------------------------------

DECLARE SUB Rozdaj_karty()

SUB Rozdaj_karty()

  DIM AS INTEGER i,j,k

  k = 1
  FOR i = 1 TO 4
    FOR j = 1 TO 13
      gracz(i,j) = talia(k)
      k += 1
    NEXT
  NEXT
END SUB

' Procedura sortuje karty gracza wg kolorów i figur
'--------------------------------------------------------

DECLARE SUB Sortuj_karty(BYVAL g AS INTEGER)

SUB Sortuj_karty(BYVAL g AS INTEGER)

  DIM karty(0 TO 3,0 TO 12) AS TKarta
  DIM AS INTEGER lfig(0 TO 12),lkol(0 TO 3),i,j
  DIM f AS TFigura
  DIM k AS TKolor

' Ustawiamy liczniki figur

  FOR f = F_A TO F_2: lfig(f) = 0: NEXT

' Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
' figur wg figury

  FOR i = 1 TO 13
     f = gracz(g,i).Figura
     karty(lfig(f),f) = gracz(g,i)
     lfig(f) += 1
  NEXT

' Przeglądamy tablicę figur pobierając z niej karty do ręki gracza

  i = 1
  FOR f = F_A TO F_2
    FOR j = 0 TO lfig(f) - 1
      gracz(g,i) = karty(j,f)
      i += 1
    NEXT
  NEXT

' Ustawiamy liczniki kolorów

  FOR k = K_PIK TO K_TREFL: lkol(k) = 0: NEXT

' Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
' kolorów wg koloru karty

  FOR i = 1 TO 13
    k = gracz(g,i).Kolor
    karty(k,lkol(k)) = gracz(g,i)
    lkol(k) += 1
  NEXT

' Przeglądamy tablicę kolorów pobierając z niej karty do ręki gracza

  i = 1
  FOR k = K_PIK TO K_TREFL
    FOR j = 0 TO lkol(k) - 1
      gracz(g,i) = karty(k,j)
      i += 1
    NEXT
  NEXT
END SUB

' Procedura wyświetla karty gracza wg jego numeru:
' 1 : gracz u góry    (15,1)
' 2 : gracz po prawej (30,6)
' 3 : gracz u dołu    (15,11)
' 4 : gracz po lewej  (1,6)
' okna konsoli. Wydruk zajmuje 4 wiersze, w każdym do 15 znaków.
' Figurę 10 wyświetlamy jako T - każda karta powinna zajmować jeden
' znak, a zapis 10 wymaga dwóch znaków.
'--------------------------------------------------------

DECLARE SUB Wyswietl_karty(BYVAL g AS INTEGER)

SUB Wyswietl_karty(BYVAL g AS INTEGER)

  DIM kolory AS STRING * 4
  DIM figury AS STRING * 13
  DIM px(1 TO 4) AS INTEGER => {15,30,15,1}
  DIM py(1 TO 4) AS INTEGER => {1,6,11,6}
  DIM i AS INTEGER, k AS TKolor

  kolory = CHR$(6) + CHR$(3) + CHR$(4) + CHR$(5)
  figury = "AKDWT98765432"
  FOR k = K_PIK TO K_TREFL
    LOCATE py(g) + k, px(g)
    PRINT MID$(kolory, 1 + k, 1);" ";
    FOR i = 1 TO 13
      IF gracz(g,i).Kolor = k THEN
        PRINT MID$(figury, 1 + gracz(g,i).Figura, 1);
      END IF
    NEXT  
  NEXT
END SUB

'---------------
' Program główny
'---------------

DIM i AS INTEGER

RANDOMIZE
Inicjuj_talie()
Tasuj_talie()
Rozdaj_karty()
FOR i = 1 TO 4
  Sortuj_karty(i)
  Wyswietl_karty(i)
NEXT
LOCATE 16,1
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="frmdistsort">
      <h3 style="text-align: center">Sortowanie Kart</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>
      <div align="center">
        <table border="0" id="table194" cellpadding="8"
               style="border-collapse: collapse" bgcolor="#FFFFFF">
          <tr>
            <td>&nbsp;</td>
            <td><span id="tg1">.</span></td>
            <td>&nbsp;</td>
          </tr>
          <tr>
            <td><span id="tg4">.</span></td>
            <td bgcolor="#009900" style="border: 4px solid #006600">&nbsp;</td>
            <td><span id="tg2">.</span></td>
          </tr>
          <tr>
            <td>&nbsp;</td>
            <td><span id="tg3">.</span></td>
            <td>&nbsp;</td>
          </tr>
        </table>
      </div>
    </form>

<script language="javascript">

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

// Deklaracje zmiennych globalnych
//--------------------------------------------------------

var talia = new Array();
var gracz = new Array()
var i,j;

for(i = 0; i < 52; i++) talia[i] = new Object();
for(i = 0; i < 4; i++)
{
  gracz[i] = new Array();
  for(j = 0; j < 13; j++) gracz[i][j] = new Object();
}

// Definicje procedur i funkcji
//--------------------------------------------------------

// Procedura inicjuje talię kart
//--------------------------------------------------------
function Inicjuj_talie()
{
  var i,k,f

  k = f = 0;
  for(i = 0; i < 52; i++)
  {
    talia[i].Kolor = k; talia[i].Figura = f;
    f++;
    if(f == 13)
    {
      k++; f = 0;
    }
  }
}

// Procedura tasuje talię kart
//--------------------------------------------------------
function Tasuj_talie()
{
  var i,a,b;
  var x = new Object();

  for(i = 0; i < 1000; i++)
  {
    a = Math.floor(Math.random() * 52); b = Math.floor(Math.random() * 52);
    x = talia[a]; talia[a] = talia[b]; talia[b] = x;
  }
}

// Procedura rozdaje karty poszczególnym graczom
//--------------------------------------------------------
function Rozdaj_karty()
{
  var i,j,k;

  k = 0;
  for(i = 0; i < 4; i++)
    for(j = 0; j < 13; j++) gracz[i][j] = talia[k++];
}

// Procedura sortuje karty gracza wg kolorów i figur
//--------------------------------------------------------
function Sortuj_karty(g)
{
  var karty = new Array();
  var lfig  = new Array()
  var lkol  = new Array()
  var i,j,f,k;

  for(i = 0; i < 4; i++)
  {
    karty[i] = new Array(); 
    for(j = 0; j < 13; j++) karty[i][j] = new Object();
  }

// Ustawiamy liczniki figur

  for(f = 0; f < 13; f++) lfig[f] = 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// figur wg figury

  for(i = 0; i < 13; i++)
  {
    f = gracz[g][i].Figura;
    karty[lfig[f]++][f] = gracz[g][i];
  }

// Przeglądamy tablicę figur pobierając z niej karty do ręki gracza

  i = 0;
  for(f = 0; f < 13; f++)
    for(j = 0; j < lfig[f]; j++) gracz[g][i++] = karty[j][f];

// Ustawiamy liczniki kolorów

  for(k = 0; k < 4; k++) lkol[k] = 0;

// Przeglądamy rękę gracza i umieszczamy kolejne karty w tablicy
// kolorów wg koloru karty

  for(i = 0; i < 13; i++)
  {
    k = gracz[g][i].Kolor;
    karty[k][lkol[k]++] = gracz[g][i];
  }

// Przeglądamy tablicę kolorów pobierając z niej karty do ręki gracza

  i = 0;
  for(k = 0; k < 4; k++)
    for(j = 0; j < lkol[k]; j++) gracz[g][i++] = karty[k][j];
}

// Procedura wyświetla karty gracza wg jego numeru:
// 0 : gracz u góry
// 1 : gracz po prawej
// 2 : gracz u dołu
// 3 : gracz po lewej
// okna konsoli. Wydruk zajmuje 4 wiersze, w każdym do 15 znaków.
// Figurę 10 wyświetlamy jako T - każda karta powinna zajmować jeden
// znak, a zapis 10 wymaga dwóch znaków.
//--------------------------------------------------------
function Wyswietl_karty(g)
{
  var kolory = new Array("&#9824;","&#9829;","&#9830;","&#9827;");
  var figury = "AKDWT98765432";
  var i,k,t;

  t = "";

  for(k = 0; k < 4; k++)
  {
    switch(k)
    {
      case 0:
      case 3: t += "<font color='black'>"; break;
      case 1:
      case 2: t += "<font color='red'>"; break;
    }
    t += kolory[k] + " ";
    for(i = 0; i < 13; i++)
      if(gracz[g][i].Kolor == k) t += figury.charAt(gracz[g][i].Figura);
    t += "</font><br>"
  }
  g++;
  document.getElementById("tg" + g).innerHTML = t;
}

//---------------
// Program główny
//---------------

function main()
{
  var i;

  Inicjuj_talie();
  Tasuj_talie();
  Rozdaj_karty();
  for(i = 0; i < 4; i++)
  {
    Sortuj_karty(i); Wyswietl_karty(i);
  }
}

</script>

  </body>
</html>

 

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

Sortowanie Kart

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


  .  
.   .
  .  

 

 


Zobacz również na:

Sortowanie kubełkowe 1 | 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.