Sortowanie Pozycyjne
           Radix Sort


Podrozdziały     Tematy pokrewne

Algorytm

Pozycją (ang. radix) nazywamy miejsce cyfry w zapisie liczby. Sortowanie pozycyjne polega na sortowaniu elementów wg kolejnych (licząc od końca) cyfr liczby. Algorytm sortujący musi być stabilny, tzn. nie może zmieniać kolejności elementów równych, w przeciwnym razie efekty poprzednich sortowań zostaną utracone.

 

Przykład:

Posortować algorytmem sortowania pozycyjnego zbiór liczb:

{ 547 398 247 153 121 792 421 }

Liczby posortujemy wg kolejnych od końca cyfr:

 

start ??x ?x? x?? koniec
547
398
247
153
121
792
421
121
421
792
153
547
247
39
8
121
421
547
247
153
792
398
121
153
247
398
421
547
792
121
153
247
398
421
547
792

 

Po posortowaniu ostatniej cyfry liczby tworzą ciąg posortowany.

Sortowanie wg poszczególnych cyfr możemy przeprowadzić w czasie liniowym. Operację musimy wykonać tyle razy, z ilu cyfr zbudowane są liczby reprezentujące sortowane elementy. Jeśli liczby są równomiernie rozłożone w reprezentowanym zbiorze, to n elementów może mieć do (logpn + 1) cyfr, gdzie p jest podstawą systemu zapisu liczb. Zatem czas sortowania będzie proporcjonalny do iloczynu n(logpn + 1). Klasa złożoności obliczeniowej jest równa O(n log n).

 

Przykład:

Posortować algorytmem sortowania pozycyjnego zbiór liczb binarnych:

{100111 111011 011101 101011 001111 101000 110011 100001 101101 111111 000011}

 

start   koniec
100111
111011
011101
101011
001111
101000
110011
100001
101101
111111
000011
101000
100111
111011
011101
101011
001111
110011
100001
101101
111111
000011
101000
011101
100001
101101
100111
111011
101011
001111
110011
111111
000011
101000
100001
111011
101011
110011
000011
011101
101101
100111
001111
111111
100001
110011
000011
100111
101000
111011
101011
011101
101101
001111
111111
100001
000011
100111
101000
101011
101101
001111
110011
111011
011101
111111
000011
001111
011101
100001
100111
101000
101011
101101
110011
111011
111111
000011
001111
011101
100001
100111
101000
101011
101101
110011
111011
111111

 

Sortowanie wg bitów jest bardzo proste, jednakże mało efektywne. Lepszym rozwiązaniem jest przyjęcie za podstawę p liczby będącej potęgą 2, np. 24 lub 28. W takim przypadku sortujemy wg grup bitów (dla 24 - grupy 4 bitów, dla 28 - grupy 8 bitów). Zgodnie z podanym wcześniej wzorem klasa czasowej złożoności obliczeniowej będzie równa:

 

dla p = 24 :  O(n log16 n)
dla p = 28O(n log256 n)

 

Oba wzory sprowadzają się do O(n log n) (udowodnij to), lecz sortowanie wykonywane jest odpowiednio 4 i 8 razy szybciej (mniejsze współczynniki proporcjonalności c).

Jako algorytm sortujący idealnie pasuje opisany w poprzednim rozdziale algorytm sortowania przez zliczanie.

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów w sortowanym zbiorze, n N
d[ ] - sortowany zbiór danych. Indeksy elementów rozpoczynają się od wartości 1.
MAXel - maksymalna wartość sortowanych elementów

Dane wyjściowe

d[ ] - posortowany rosnąco zbiór danych

Zmienne pomocnicze

b[ ] - pomocniczy zbiór danych. Indeksy elementów rozpoczynają się od 1.
m - maska bitowa do wydzielania bitu z elementu, m N
i - zmienna sterująca pętli, i N
L0 - licznik bitów 0, L0 N
L1 - licznik bitów 1, L1 N

 

Lista kroków

Sortuj(z1[ ], z2[ ], m)

K01: L0 ← 0;  L1 ← 0
K02: Dla i = 1,2,...,n: wykonuj K03
K03:     Jeśli z1[i] ∧ m ≠ 0, to
        L1 ← L1 + 1
    inaczej
        L0 ← L0 + 1
K04: L1 ← L1 + L0
K05: Dla i = n, n - 1,...,1: wykonuj K06
K06:     Jeśli z1[i] ∧ m ≠ 0, to
        z2[L1] ← z1[i];  L1 ← L1 - 1
    inaczej
        z2[L0] ← z1[i];  L0 ← L0 - 1
K07: Zakończ

 

Główny algorytm sortowania pozycyjnego

K01: m ← 1
K02: Dopóki m ≤ MAXel wykonuj K03...K06
K03:     Sortuj(d[ ], b[ ], m)
K04:     Przesuń bity maski m o jeden w lewo
K05:     Sortuj(b[ ], d[ ], m)
K06:     Przesuń bity maski m o jeden w lewo
K07: Zakończ

 

Schemat blokowy

flow

 

Zasada pracy algorytmu sortowania pozycyjnego jest bardzo prosta. Ustawiamy maskę bitową m tak, aby bit b0 miał wartość 1. Następnie w pętli warunkowej wywołujemy procedurę sortowania przez zliczanie przekazując jej jako parametry sortowany zbiór danych d[ ] oraz zbiór pomocniczy b[ ], w którym znajdzie się wynik sortowania, i maskę m. Przesuwamy bity maski o jeden w lewo. Jeszcze raz wywołujemy procedurę sortującą (zwróć uwagę na zamienioną kolejność zbiorów - sortowany jest b[ ], a wynik trafia z powrotem do d[ ]) i przesuwamy bity maski o jeden w lewo.

Procedura sortująca działa wg opisanego w poprzednim rozdziale algorytmu sortowania przez zliczanie:

Zerujemy liczniki bitu 0 oraz bitu 1. W pierwszej pętli zliczamy bity 0 i 1. Następnie obliczamy ostatnie pozycje dla elementów zawierających odpowiednio bit 0 i bit 1. Przepisujemy elementy ze zbioru wejściowego na odpowiadające im pozycje w zbiorze wyjściowym.

 

Programy

Efekt uruchomienia programu
  Sortowanie pozycyjne
------------------------
 (C)2005 Jerzy Walaszek

Przed sortowaniem:

 479 964 207  34 789  26 943 371 364 245 413 774 740 391  98 512 952 109 426 671
 340  59 614 712 577 384 730 460 463 515 312 737 635 510  60 214 514 226 178 494
 652 468 869 792 852 638 417  22 542 633 507   6  98 905 448 358 569 129 723 323
 373 777 147 251 862 341 428 992 402 128 196 528 572  65 690 484 569 733 898 238

Po sortowaniu:

   6  22  26  34  59  60  65  98  98 109 128 129 147 178 196 207 214 226 238 245
 251 312 323 340 341 358 364 371 373 384 391 402 413 417 426 428 448 460 463 468
 479 484 494 507 510 512 514 515 528 542 569 569 572 577 614 633 635 638 652 671
 690 712 723 730 733 737 740 774 777 789 792 852 862 869 898 905 943 952 964 992

 

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

program RadixSort;

const
  N     =  80;  // ilość elementów
  MAXEL = 999;  // maksymalna wartość elementu

type
  TZbior = array[1..N] of cardinal;

// Procedura sortująca

procedure Sortuj(var z1,z2 : TZbior; m : cardinal);
var
  L : array[boolean] of cardinal;
  i : cardinal;
  t : boolean;
begin
  L[false] := 0; L[true] := 0;
  for i := 1 to N do inc(L[(z1[i] and m) > 0]);
  inc(L[true], L[false]);
  for i := N downto 1 do
  begin
    t := (z1[i] and m) > 0;
    z2[L[t]] := z1[i];
    dec(L[t]);
  end;
end;

var
  d,b : TZbior;
  i   : integer;
  m   : cardinal;

begin
  writeln('  Sortowanie pozycyjne  ');
  writeln('------------------------');
  writeln(' (C)2005 Jerzy Walaszek ');
  writeln;

// Generujemy pseudolosową zawartość zbioru d[ ]

  randomize;
  for i := 1 to N do d[i] := random(MAXEL + 1);
  writeln('Przed sortowaniem:');
  writeln;
  for i := 1 to N do write(d[i]:4);

// Ustawiamy maskę na najmłodszy bit

  m := 1;

// Sortujemy

  while m <= MAXEL do
  begin
    Sortuj(d,b,m); m := m shl 1;
    Sortuj(b,d,m); m := m shl 1;
  end;

// Wyświetlamy wyniki

  writeln;
  writeln('Po sortowaniu:');
  writeln;
  for i := 1 to N do write(d[i]:4);
  writeln;
  writeln('KONIEC. Nacisnij klawisz Enter...'); readln;
end.
Code::Blocks
// Sortowanie Pozycyjne
//--------------------------------------------------------
// (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     =  80;  // ilość elementów
const int MAXEL = 999;  // maksymalna wartość elementu

// Procedura sortująca

void Sortuj(unsigned z1[], unsigned z2[], unsigned m)
{
  unsigned L[2],i;

  L[0] = L[1] = 0;
  for(i = 1; i <= N; i++) L[(z1[i] & m) > 0]++;
  L[1] += L[0];
  for(i = N; i >= 1; i--) z2[L[(z1[i] & m) > 0]--] = z1[i];
}

int main()
{
  unsigned d[N+1],b[N+1],i,m;

  cout << "  Sortowanie pozycyjne  \n"
          "------------------------\n"
          " (C)2005 Jerzy Walaszek \n\n"
          "Przed sortowaniem:\n\n";
          
// Generujemy pseudolosową zawartość zbioru d[ ]

  srand((unsigned)time(NULL));

  for(i = 1; i <= N; i++)
  {
    d[i] = rand() % (MAXEL + 1);
    cout << setw(4) << d[i];
  }
  
// Ustawiamy maskę na najmłodszy bit

  m = 1;

// Sortujemy

  while(m <= MAXEL)
  {
    Sortuj(d,b,m); m <<= 1;
    Sortuj(b,d,m); m <<= 1;
  }

// Wyświetlamy wyniki

  cout << "\nPo sortowaniu:\n\n";
  for(i = 1; i <= N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}  
Free Basic
' Sortowanie Pozycyjne
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

OPTION EXPLICIT

CONST N     =  80  ' ilość elementów
CONST MAXEL = 999  ' maksymalna wartość elementu

' Procedura sortująca

DECLARE SUB Sortuj(z1() AS UINTEGER, z2() AS UINTEGER, BYVAL m AS UINTEGER)
SUB Sortuj(z1() AS UINTEGER, z2() AS UINTEGER, BYVAL m AS UINTEGER)

  DIM AS UINTEGER L0,L1,i
  
  L0 = 0: L1 = 0
  FOR i = 1 TO N
    IF (z1(i) AND m) > 0 THEN
      L1 += 1
    ELSE
      L0 += 1
    END IF
  NEXT
  L1 += L0
  FOR i = N TO 1 STEP -1
    IF (z1(i) AND m) > 0 THEN
      z2(L1) = z1(i): L1 -= 1
    ELSE
      z2(L0) = z1(i): L0 -= 1
    END IF
  NEXT
END SUB

DIM AS UINTEGER d(N),b(N),i,m

PRINT "  Sortowanie pozycyjne  "
PRINT "------------------------"
PRINT " (C)2005 Jerzy Walaszek "
PRINT

' Generujemy pseudolosową zawartość zbioru d( )

RANDOMIZE
FOR i = 1 TO N: d(i) = INT(RND(1) * (MAXEL + 1)): NEXT
PRINT "Przed sortowaniem:"
PRINT
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

' Ustawiamy maskę na najmłodszy bit

m = 1

' Sortujemy

WHILE m <= MAXEL
  Sortuj(d(),b(),m): m = m SHL 1
  Sortuj(b(),d(),m): m = m SHL 1
WEND

' Wyświetlamy wyniki

PRINT
PRINT "Po sortowaniu:"
PRINT
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT
PRINT "KONIEC. 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="frmradixsort">
      <h3 style="text-align: center">Sortowanie Pozycyjne</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 Pozycyjne
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N     =  80; // ilość elementów
var MAXEL = 999; // maksymalna wartość elementu

// Procedura sortująca

function Sortuj(z1,z2,m)
{
  var L0,L1,i;

  L0 = L1 = 0;
  for(i = 1; i <= N; i++) if((z1[i] & m) > 0) L1++; else L0++;
  L1 += L0;
  for(i = N; i >= 1; i--)
    if((z1[i] & m) > 0) z2[L1--] = z1[i]; else z2[L0--] = z1[i]; 
}

function main()
{
  var d = new Array(N + 1);
  var b = new Array(N + 1);
  var i,m,t;

  t = "Przed sortowaniem:<BR><BR>";

// Generujemy pseudolosową zawartość zbioru d[ ]

  for(i = 1; i <= N; i++)
  {
    d[i] = Math.floor(Math.random() *(MAXEL + 1));
    t += " " + d[i];
  }

// Ustawiamy maskę na najmłodszy bit

  m = 1;

// Sortujemy

  while(m <= MAXEL)
  {
    Sortuj(d,b,m); m <<= 1;
    Sortuj(b,d,m); m <<= 1;
  }

// Wyświetlamy wyniki

  t += "<BR><BR>Po sortowaniu:<BR><BR>";
  for(i = 1; i <= N; i++) t += " " + d[i];
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

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

Sortowanie Pozycyjne

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


...

 


Zobacz również na:

Sortowanie rozrzutowe | Sortowanie kubełkowe 1 | Listy | Sortowanie kubełkowe 2 | Sortowanie przez zliczanie

 



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.