Strona główna » Algorytmy » Sortowanie » Sortowanie Pozycyjne Liczb
 

Sortowanie Pozycyjne Liczb

https://mattomatti.com/fs14

Wstęp

Sortowanie Pozycyjne Liczb jest bardzo podobne do Sortowania Pozycyjnego Słów, ale należy pamiętać, że w tym przypadku kolejne znaki wybiera się na trochę innych zasadach niż znaki ze słów. Dowodzi się, że algorytm działa dla części danych wejściowych szybciej niż Sortowanie szybkie.

Opis sortowania

Algorytm Sortowania Pozycyjnego wymaga, aby wszystkie porównywane wartości miały tę samą długość. Z punktu zapisu liczby nie zawsze mają tyle samo cyfr, ale nic nie przeszkodzi, aby na początku dopisać kilka zer. Oczywiście nie trzeba sztucznie dopisywać, a wystarczy pamiętać, że jeśli i-ta cyfra nie jest zapisana w liczbie to przyjmujemy wartość 0.

W każdej iteracji zliczamy ile jest na i-tej pozycji wystąpień każdej z cyfry. Na podstawie ilości wystąpień generujemy miejsca zapisu kolejnych liczb i na tej podstawie generujemy listę końcową. Podczas tego procesu algorytm potrzebuje dodatkowej przestrzeni, aby ustawić w kolejności przepisywane elementy. Algorytm można zastosować nie tylko do sortowania w systemie dziesiętnym, ale również do innych systemów liczbowych. DLa niektórych sposób wybierania cyfr nieznacznie się skomplikuje.

Przykład

Weźmy przykładowo listę L:={31, 5, 21, 9, 8, 96, 20, 12}. Dla uproszczenia mamy liczby co najwyżej dwucyfrowe. Będzie sortować wybierając cyfry w systemie dziesiętnym. Oznacza to, że do wykonania będą dwie iteracje każda sortująca kolejną cyfrę. Wyznaczmy liczniki dla każdej cyfry:

Liczba3152198962012
Pobrana cyfra15198602

Następnie sortujemy te liczby na podstawie pobranej wartości cyfry i przechodzimy do kolejnej cyfry.

Liczba2031211259689
Pobrana cyfra23210900

Sortując ponownie na podstawie pobranych cyfr otrzymujemy posortowaną listę liczb:

Liczba5891220213196

Złożoność

Przyjmując, że będziemy wybierać wartości z pewnego systemu b, a najdłuższa liczba składa się z m = logb(k) cyfr, gdzie k to największa wartość. W każdej z m iteracji wykonujemy n pobierań i-tej cyfry, konwersja liczników ma długość b, a późniejsze przepisywanie składa się z dwóch pętli po n przepisań. Wtedy złożoność algorytmu wynosi: O(m·(3n + b)). Dla dużych list n 〉 b, więc złożoność można uprościć do O(n·logb(k)). W przypadku wybrania b = k możemy otrzymać nawet złożoność liniową O(n), ale należy pamiętać, że złozoność pamięciowa będzie znacznie większa.

Złożoność pamięciowa dotyczy przechowywania b liczników oraz n uporządkowanych wartości, więc wynosi ona O(n + b). Pryjmując ponownie, że n 〉 b otrzymamy ponownie złożoność liniową O(n).

Implementacja

Funkcja Główna

Funkcja główna zarządza pamięcią oraz przygotowuje dane do sortowania według kolejnych cyfr.

C++
C#
  1. void sortuj(int* tab, int n) {
  2.   int max = tab[0];
  3.   for (int i = 1; i < n; i++)
  4.     if (tab[i] > max)
  5.       max = tab[i];
  6.   int* pom = new int[n];
  7.   for (int pot = 1; max / pot > 0; pot *= 10)
  8.     sortuj_pom(tab, pom, n, pot);
  9.   delete pom;
  10. }

(2. - 5.) Znajdź maksymalną liczbę na liście, aby ograniczyć sortowanie według kolejnych cyfr. Następnie (6.) deklarujemy tablicę pomocniczą. Potem (7. - 8.) sortujemy według kolejnych cyfr, a na koniec (9.) dealokujemy zerezerwowaną pamięć.

(2. - 5.) Znajdź maksymalną liczbę na liście, aby ograniczyć sortowanie według kolejnych cyfr. Następnie (6.) deklarujemy tablicę pomocniczą. Potem (7. - 8.) sortujemy według kolejnych cyfr.

Funkcja Pomocnicza

Funkcja pomocnicza przyjmuje dwa dodatkowe argumenty: są to tablica pomocnicza pom oraz potęga pot, która pomaga wybierać kolejne liczby (jej wartość w każdej iteracji jest 10 razy większa).

C++
C#
  1. void sortuj_pom(int* tab, int* pom, int n, int pot) {
  2.   int liczniki[10] = { 0 };
  3.   for (int i = 0; i < n; i++)
  4.     liczniki[(tab[i] / pot) % 10]++;
  5.   for (int i = 1; i < 10; i++)
  6.     liczniki[i] += liczniki[i - 1];
  7.   for (int i = n - 1; i >= 0; i--) {
  8.     int poz = (tab[i] / pot) % 10;
  9.     pom[liczniki[poz] - 1] = tab[i];
  10.     liczniki[poz]--;
  11.   }
  12.   for (int i = 0; i < n; i++)
  13.     tab[i] = pom[i];
  14. }

(2.) Deklarujemy tablicę liczników. Następnie (3. - 4.) zliczamy ile jest wystąpień każdej cyfry. Na tej podstawie (5. - 6.) możliwe jest wyznaczenie na których pozycjach należy przepisać liczbę mającą na i-tej pozycji cyfrę. Kolejna pętla (7. - 11.) przepisuje wartości z tablicy tab do tablicy pom odpowiednio jest ustawiając. Na koniec należy pamiętać o przepisaniu (12. - 13.) częściowo posortowanych danych z tablicy pomocniczej pom do głównej tab.

(2.) Deklarujemy tablicę liczników. Następnie (3. - 4.) zliczamy ile jest wystąpień każdej cyfry. Na tej podstawie (5. - 6.) możliwe jest wyznaczenie na których pozycjach należy przepisać liczbę mającą na i-tej pozycji cyfrę. Kolejna pętla (7. - 11.) przepisuje wartości z tablicy tab do tablicy pom odpowiednio jest ustawiając. Na koniec należy pamiętać o przepisaniu (12. - 13.) częściowo posortowanych danych z tablicy pomocniczej pom do głównej tab.

Testowanie funkcji

Poniższy fragment kodu wczyta od użytkownika ile liczb ma tablica, następnie wczyta n wartości i wypisze posortowaną listę.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj ile jest elementow\n n = ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   sortuj(tab, n);
  10.   cout << "Po posortowaniu:\n";
  11.   for (int i = 0; i < n; i++)
  12.     cout << tab[i] << " ";
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Napisz implementację sortowania pozycyjnego, który pozwala wybrać system liczbowy, który określi pulę cyfr do posortowania. Zakładamy, że wprowadzona przez użytkownika będzie składać się z liczb zapisanych dziesiętnie i również dziesiętnie liczby mają zostać wypisane w posortowanej liście. Przetestuj działanie programu.