Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
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 398 |
121 421 547 247 153 792 398 |
121 153 247 398 421 547 792 |
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 (
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 |
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 = 28 : O(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.
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 |
d[ ] | - posortowany rosnąco zbiór danych |
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 |
K01: | L0 ← 0; L1 ← 0 |
K02: | Dla i = 1,2,...,n: wykonuj krok 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 krok 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 |
K01: | m ← 1 |
K02: | Dopóki m
≤ MAXel: wykonuj kroki 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 |
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
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.
C++// 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; } |
Pascal// 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. |
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> |
Wynik: |
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 |
Zobacz również na:
Sortowanie rozrzutowe | Sortowanie
kubełkowe 1 | Listy | Sortowanie
kubełkowe 2 | Sortowanie przez zliczanie
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.