Rys historyczny

Początki sortowania pozycyjnego sięgają $\text{XIX}$ wieku, kiedy to w roku $1890$ Herman Hollerith po raz pierwszy zastosował maszynę licząco‑analityczną do opracowania spisu ludności USA. Wynalazek swój opatentował w $1889$ r.

R18gYKRa2sxqT

Rysunek przedstawia maszynę licząco‑analityczną. Widoczne są zegary oraz tablica z otworami. Przy części biurkowej znajdują się matryce. Na rysunku zapisano, że została opatentowana w styczniu 1889 roku.

Sortowanie pozycyjne dat – omówienie

Algorytm, którym się zajmujemy, jest bardzo podobny do algorytmu sortowania pozycyjnego słówPXnUDqfi5algorytmu sortowania pozycyjnego słów oraz sortowania pozycyjnego liczbPjBWIbxmPsortowania pozycyjnego liczb.

Algorytm sortowania pozycyjnego dat polega na sortowaniu dat według cyfr na kolejnych pozycjach, rozpoczynając od najmniej znaczącej (czyli cyfry jedności dnia). Aby było to możliwe, przyjmujemy format zapisu daty, obsługiwany przez algorytm. W tym materiale wybieramy standard ISO 8601. Jednym ze sposobów zapisu daty w tym formacie jest postać RRRR‑MM‑DD.

RRRR oznacza czterocyfrowy zapis roku, np. 1998. MM oznacza dwucyfrowy zapis miesiąca, np. czerwiec zapiszemy jako 06. DD oznacza dwucyfrowy zapis dnia w danym miesiącu, np. 19. Takim sposobem otrzymujemy jednoznaczny zapis daty: 1998‑06‑19 (19 czerwca 1998 r.).

Ważne jest, aby nie pomijać wiodących zer. Błędem będzie zapisanie daty 1998‑06‑19 jako 1998‑6-19.

Przydatność tego zapisu w algorytmie wynika z następujących cech:

• cyfry są uszeregowane od najmniej znaczącej do najbardziej znaczącej (od prawej do lewej),

• długość daty jest stała i wynosi 10,

• separatory (znak myślnika) występują na z góry określonych pozycjach: jest to czwarty i siódmy indeks, przy założeniu, że liczymy od zera.

Przy tak reprezentowanej dacie algorytm sortowania pozycyjnego sprowadza się do sortowania dat według kolejnych pozycji od najmniej znaczącej do najbardziej znaczącej cyfry (od prawej do lewej), z pominięciem separatorów na odpowiednich indeksach.

Omówmy przykładowe zadanie, w którym naszym celem jest posortowanie podanego zbioru dat w kolejności niemalejącej przy użyciu algorytmu sortowania pozycyjnego.

Przykład 1

Z = {1960‑03‑21, 2003‑04‑09, 1526‑01‑30, 1680‑07‑14, 2050‑11‑02, 1250‑12‑17, 1337‑09‑05}

Daty przechowywane są zgodnie z wcześniej przyjętym formatem: RRRR‑MM‑DD.

Sortując daty, rozpatrujemy kolejne cyfry zapisu, rozpoczynając od najmniej znaczącej. Najpierw korzystając z pomocniczego stabilnego algorytmu sortowaniastabilny algorytm sortowaniastabilnego algorytmu sortowania, sortujemy daty kolejno według:

• cyfry jedności liczby reprezentującej dni,

• cyfry dziesiątek liczby reprezentującej dni,

R16nMWBEDrjSu

Ilustracja przedstawia zapisy dat. Są zapisane w trzech kolumnach, pomiędzy każdą kolumną dat jest strzałka w prawo w kierunku następnej kolumny. Daty zapisane w pierwszej kolumnie: 1998‑11‑12, 1998‑11‑13, 1534‑12‑01, 1667‑04‑04, 1804‑07‑15. Strzałka do kolejnej kolumny dat: od góry - 1534‑12‑01, 1998‑11‑12, 1998‑11‑13, 1667‑04‑04, 1804‑07‑15. Pionowo żółtym paskiem zaznaczono ostatnie cyfry z każdego rzędu dat, czyli 1, 2, 3, 4, 5. Strzałka do ostatniej, trzeciej kolumny dat. Od góry: 1534‑12‑01, 1667‑04‑04, 1998‑11‑12, 1998‑11‑13, 1804‑07‑15. Pionowym żółtym paskiem zaznaczono przedostatnie cyfry w zapisie dat, czyli 0, 0, 1, 1, 1.

• cyfry jedności liczby reprezentującej miesiąc,

• cyfry dziesiątek liczby reprezentującej miesiąc,

RRRYt3bgLe1dT

Ilustracja przedstawia zapisy dat. Są zapisane w trzech kolumnach, pomiędzy każdą kolumną dat jest strzałka w prawo w kierunku następnej kolumny. Daty zapisane w pierwszej kolumnie: Od góry: 1534‑12‑01, 1667‑04‑04, 1998‑11‑12, 1998‑11‑13, 1804‑07‑15. Strzałka w prawo do środkowej kolumny z datami od góry: 1998‑11‑12, 1998‑11‑13, 1534‑12‑01, 1667‑04‑04, 1804‑07‑15. Pionowym żółtym paskiem zaznaczono cyfry trzecie od końca w zapisie dat, czyli 1, 1, 2, 4, 7. Strzałka w prawo do ostatniej kolumny z datami: 1667‑04‑04, 1804‑07‑15, 1998‑11‑12, 1998‑11‑13, 1534‑12‑01. Pionowym żółtym paskiem zaznaczono czwartą od końca cyfrę w każdej dacie, czyli od góry: 0, 0, 1, 1, 1.

• cyfry jedności liczby reprezentującej rok,

• cyfry dziesiątek liczby reprezentującej rok,

• cyfry setek liczby reprezentującej rok,

• cyfry tysięcy liczby reprezentującej rok.

RnC55wcZCwzUW

Ilustracja przedstawia pięć kolumn z zapisami dat. Pomiędzy kolumnami są poziome strzałki. Daty w pierwszej kolumnie od góry: 1667‑04‑04, 1804‑07‑15, 1998‑11‑12, 1998‑11‑13, 1534‑12‑01. Strzałka w prawo do drugiej kolumny: 1804‑07‑15, 1534‑12‑01, 1667‑04‑04, 1998‑11‑12, 1998‑11‑13. Pionowym żółtym paskiem zaznaczono ostatnia cyfrę z każdego roku, czyli od góry: 4, 4, 7, 8, 8. Strzałka w prawo do środkowej kolumny. Tu daty: 1804‑07‑15, 1534‑12‑01, 1667‑04‑04, 1998‑11‑12, 1998‑11‑13. Pionowym żółtym paskiem zaznaczono w każdym roku druga cyfrę od końca, czyli od góry kolejno: 0, 3, 6, 9, 9. Strzałka w prawo do przedostatniej kolumny: 1534‑12‑01, 1667‑04‑04, 1804‑07‑15, 1998‑11‑12, 1998‑11‑13. Pionowym żółtym paskiem zaznaczono drugą cyfrę w każdej dacie, czyli: 5, 6, 8, 9, 9. Strzałka w prawo do ostatniej kolumny: 1534‑12‑01, 1667‑04‑04, 1804‑07‑15, 1998‑11‑12, 1998‑11‑13. Pionowym żółtym paskiem zaznaczono pierwszą cyfrę roku, czyli kolejno od góry: 1, 1, 1, 1, 1.

Po wykonaniu ostatniego kroku lista dat jest posortowana.

Zasada działania algorytmu sortowania pozycyjnego dat

Do posortowania elementów na konkretnych, odpowiadających sobie pozycjach w datach możemy użyć dowolnego algorytmu sortowania stabilnegostabilny algorytm sortowaniaalgorytmu sortowania stabilnego.

Algorytm pomocniczy musi być stabilnym algorytmem sortowania – w przeciwnym wypadku sortowanie dat według kolejnych pozycji nie miałoby sensu. Np. przy sortowaniu dat: 1998‑11‑05 i 1998‑11‑06 po poprawnym posortowaniu według cyfry jedności dni, algorytm bez gwarancji stabilności mógłby zamienić daty, sortując według pozostałych, jednakowych cyfr. W konsekwencji: również sam algorytm sortowania pozycyjnego jest stabilny.

W tym e‑materiale jako algorytm pomocniczy wybieramy sortowanie kubełkowe, ze względu na znaną z góry liczbę kubełków równą 10 (liczba cyfr w systemie dziesiętnym). Algorytm ten został dokładnie omówiony w e‑materiale Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

Na początku wydzielamy kubełki, które posłużą za miejsce do przechowania liczb w trakcie wykonywanych operacji. Każdy kubełek oznaczamy jedną cyfrą. Musimy mieć przewidziany oddzielny kubełek dla każdej z cyfr w zależności od zastosowanego systemu liczbowego, w którym zapisana jest data.

Kubełki służą do tego, by w momencie wykonywania operacji przechować daty, które mają tę samą cyfrę na analizowanej pozycji (czyli np. w wyniku analizy cyfr jedności w liczbie dni takie daty jak 1995‑12‑25 oraz 2001‑09‑15 znalazłyby się w jednym kubełku). Następnie „wyjmujemy” wszystkie daty z kubełków w kolejności, w jakiej je tam wstawiliśmy. Dzięki temu możemy mówić o posortowaniu liczb stabilnie według odpowiedniej cyfry (w tym przykładzie według cyfry jedności w liczbie dni).

Wielokrotne powtórzenie tego procesu dla kolejnych cyfr (od najmniej do najbardziej znaczącej) pozwoli szybko otrzymać oczekiwane rezultaty. Zasada gospodarowania kubełkami jest prosta: istnieje tyle kubełków, ile jest cyfr w analizowanym systemie liczbowym. Następnie sprawdzamy, jaka cyfra znajduje się na aktualnie rozpatrywanej pozycji, i dopasowujemy ją do kubełka.

Przykład sortowania pozycyjnego dat z użyciem sortowania kubełkowego

Posortujmy niemalejąco następujący zestaw dat:

• 1960‑03‑21

• 2003‑04‑09

• 1526‑01‑30

• 1680‑07‑14

• 2050‑11‑02

• 1250‑12‑17

• 1337‑09‑05

Algorytm będzie pracował na datach zapisanych w zbiorze dat. Wygląda on następująco:

AIndeks dolny 0₀ = {1960‑03‑21, 2003‑04‑09, 1526‑01‑30, 1680‑07‑14, 2050‑11‑02, 1250‑12‑17, 1337‑09‑05}

Tak przygotowany zbiór dat możemy zacząć sortować przy użyciu pomocniczego, stabilnego algorytmu sortowania kubełkowego. Umieszczamy daty w kubełkach na podstawie aktualnie sprawdzanej cyfry. Zaczynamy od ostatniej cyfry daty, czyli mniej znaczącej cyfry opisującej dzień:

Następnie wyjmujemy daty z kubełków, zaczynając od kubełka 0:

AIndeks dolny 1₁ = {1526‑01‑30, 1960‑03‑21, 2050‑11‑02, 1680‑07‑14, 1337‑09‑05, 1250‑12‑17, 2003‑04‑09}

Posortowaliśmy daty według cyfry jedności dnia. Teraz powtarzamy proces dla przedostatniej pozycji, sortując przy tym daty według cyfr dziesiątek w numerze oznaczającym dzień:

Ponownie wyjmujemy daty z każdego kubełka. Niektóre kubełki zawierają więcej niż jedną wartość. W takim przypadku ważne jest, abyśmy wyciąganie zaczynali od daty umieszczonej najwcześniej, czyli zapisanej najniżej. Jest to istotne dla zachowania zasady sortowania stabilnego:

AIndeks dolny 2₂ = {2050‑11‑02, 1337‑09‑05, 2003‑04‑09, 1680‑07‑14, 1250‑12‑17, 1960‑03‑21, 1526‑01‑30}

Następnie przetwarzamy pozycję, na której w przyjętym zapisie daty znajduje się znak „-”. Pomijamy go i przechodzimy do przetwarzania kolejnej pozycji.

Docieramy do porządkowania według cyfry jedności liczby miesiąca:

Umieszczamy daty w tablicy zgodnie z zasadami:

AIndeks dolny 3₃ = {2050‑11‑02, 1526‑01‑30, 1250‑12‑17, 1960‑03‑21, 2003‑04‑09, 1680‑07‑14, 1337‑09‑05}

Ponownie umieszczamy wszystkie daty w kubełkach, tym razem zwracając uwagę na bardziej znaczącą cyfrę miesiąca:

Zbiór dat ma obecnie postać:

AIndeks dolny 4₄ = {1526‑01‑30, 1960‑03‑21, 2003‑04‑09, 1680‑07‑14, 1337‑09‑05, 2050‑11‑02, 1250‑12‑17}

Ponownie na kolejnej pozycji znajduje się znak „-”, więc pomijamy go.

Następnie przechodzimy do sortowania według cyfry jedności roku:

Ponownie wyjmujemy wszystkie daty. Teraz zbiór dat prezentuje się następująco:

AIndeks dolny 5₅ = {1960‑03‑21, 1680‑07‑14, 2050‑11‑02, 1250‑12‑17, 2003‑04‑09, 1526‑01‑30, 1337‑09‑05}

Wykonanie algorytmu dla cyfry dziesiątek roku poskutkuje powstaniem kubełków:

Otrzymujemy następującą listę:

AIndeks dolny 6₆ = {2003‑04‑09, 1526‑01‑30, 1337‑09‑05, 2050‑11‑02, 1250‑12‑17, 1960‑03‑21, 1680‑07‑14}

Przedostatni przebieg algorytmu (dla cyfry setek roku) utworzy następującą strukturę:

Po wypisaniu dat w odpowiedniej kolejności otrzymujemy:

AIndeks dolny 7₇ = {2003‑04‑09, 2050‑11‑02, 1250‑12‑17, 1337‑09‑05, 1526‑01‑30, 1680‑07‑14, 1960‑03‑21}

Pozostaje ostatnie powtórzenie, w którym uwzględniamy cyfrę tysięcy roku:

Wynikowy zbiór ma postać:

AIndeks dolny wyjściowa_wyjściowa = {1250‑12‑17, 1337‑09‑05, 1526‑01‑30, 1680‑07‑14, 1960‑03‑21, 2003‑04‑09, 2050‑11‑02}

Jak widać, algorytm spełnił swoje zadanie, wykonując tylko osiem powtórzeń algorytmu sortowania kubełkowego (tyle, ile jest cyfr w dacie).

Pseudokod

Zgodnie z założeniami pseudokod będzie działał na datach zapisanych w formacie RRRR‑MM‑DD. Dla innego formatu należałoby go odpowiednio dostosować.

Specyfikacja problemu:

Dane:

• rozmiar – liczba całkowita przechowująca informację dotyczącą liczby sortowanych dat

• tablica[0..rozmiar - 1] – tablica jednowymiarowa przechowująca sortowane daty w formie napisu; daty w tablicy przechowywane są jako napisy w formacie RRRR‑MM‑DD

Wynik:

• tablica[0..rozmiar - 1] – zawiera daty posortowane chronologicznie (od najwcześniejszej do najpóźniejszej)

Aby posortować daty pozycyjnie, utworzymy pętlę dla uwzględniającą wszystkie pozycje, według których powinniśmy posortować daty w tablicy tablica[]. Jest ich 10. Pominiemy również separatory znajdujące się w każdej dacie na indeksach 4 i 7 (licząc od 0).

dla pozycja = 9, 8, ..., 0 wykonuj:
  jeżeli pozycja ≠ 4 i pozycja ≠ 7:
    sortowanie_kubełkowe(pozycja)

Jak widać, skorzystaliśmy z pomocniczego sortowania kubełkowego. Przedstawmy jego zapis w postaci pseudokodu.

Niech tablica kubełki[0..9] będzie tablicą list tymczasowo przechowujących rozpatrywane aktualnie daty. ListalistaLista jest obiektem, który działa na podobnej zasadzie co tablica, lecz nie musi mieć stałego rozmiaru – można zarówno dopisywać, jak i wyciągać z niej kolejne liczby.

Funkcja kod(znak) zamienia znak znak na jego kod ASCII.

funkcja sortowanie_kubełkowe(pozycja):
  dla n = 0, 1, ..., rozmiar - 1 wykonuj:
  	// konwertuj znak tablica[n][pozycja] na liczbę z zakresu <0, 9>
    cyfra ← kod(tablica[n][pozycja]) - kod("0")
    umieść wewnątrz kubełki[cyfra] wartość tablica[n]
  
  x ← 0
  dla cyfra = 0, 1, ..., 9 wykonuj
    dopóki kubełki[cyfra] zawiera liczby wykonuj
      tablica[x] ← pobierz najwcześniej dodaną wartość z kubełki[cyfra] i usuń ją
      x ← x + 1

Cechy sortowania pozycyjnego dat

Sortowanie pozycyjne jest wydajną metodą sortowania liczb naturalnych o podobnej liczbie cyfr. Dlatego też świetnie nadaje się do sortowania dat, które w większości przypadków będą liczbami dokładnie ośmiocyfrowymi (z pominięciem ewentualnych separatorów takich jak myślniki czy kropki).

Sortowanie pozycyjne jest stabilne. A zatem jeśli w zbiorze wejściowym wystąpią powtarzające się daty, ich kolejność względem siebie się nie zmieni.

Oszacujmy złożoność czasowązłożoność czasowazłożoność czasową tego algorytmu sortowania. Wprowadźmy następujące oznaczenia:

• $N$ – liczba dat do posortowania,

• $d$ – liczba cyfr w danym formacie daty bez separatorów.

Rozpoczynamy od analizy liczby operacji dodawania i usuwania dat z kubełków w funkcji sortowanie_kubełkowe(). Instrukcje dodawania elementów do kubełków wykonają się $N$ razy. Instrukcje usuwania elementów z kubełka umieszczone w pętli dopóki wykonają się również $N$ razy (tyle, ile liczb znalazło się sumarycznie w kubełkach). Zatem złożoność obliczeniowa tej funkcji to $2 \cdot N$.

Główna pętla programu wykona się $d+2$ razy. Pomijając separatory, będzie to $d$.

W niepominiętych iteracjach (ich liczba wynosi $d$) wywołana zostanie funkcja sortowanie_kubełkowe(), której złożoność to $2 \cdot N$. Zatem złożoność całego programu to $O(d \cdot N)$.

Jeżeli przyjmiemy $d$ jako stałą równą 8, to sortowanie pozycyjne dat ma złożoność liniową.

Słownik