Algorytmy sortujące - sortowanie rozrzutowe

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 logn). 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

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.

krok 1: Przygotuj miejsce na tyle stosów, ile figur mogą mieć karty. Pierwszy stos będzie dla najstarszej karty, a ostatni dla najmłodszej.

krok 2: 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.

krok 3: 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.

krok 4: 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.

krok 5: Rozdziel karty na poszczególne stosy wg ich kolorów.

krok 6: 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

krok 7: 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.

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

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

// Sortowanie Kart
//-------------------------------------------------
// (C)2005 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.

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

#include <iostream>
#include <windows.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(void)
{
  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); system("PAUSE"); return 0;
}

' Sortowanie Kart
'-------------------------------------------------
' (C)2005 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

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

 Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

Źródło: mgr Jerzy Wałaszek

technologia programowanie algorytmy sortowanie

krok 1:	Przygotuj miejsce na tyle stosów, ile figur mogą mieć karty. Pierwszy stos będzie dla najstarszej karty, a ostatni dla najmłodszej.
krok 2:	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.
krok 3:	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.
krok 4:	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.
krok 5:	Rozdziel karty na poszczególne stosy wg ich kolorów.
krok 6:	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
krok 7:	Zakończ algorytm



		Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.