Algorytm sortowania pozycyjnego dat

Sortowanie pozycyjne operuje na zbiorach porządkowalnych leksykograficzniezbiór porządkowalny leksykograficzniezbiorach porządkowalnych leksykograficznie. Aby wykorzystać algorytm do uporządkowania tablicy dat, należy najpierw zamienić tablicę w zbiór, który będzie porządkowalny leksykograficznie, a także umożliwi łatwe przetworzenie przez komputer.

Przykładem takiego zbioru jest zbiór liczb naturalnych. Najprostszym sposobem konwersji dat na liczby jest zapisanie ich w kolejności: rok - miesiąc - dzień, co spowoduje, że cyfry znajdujące się po lewej stronie wpływają na datę w stopniu najwyższym, a te po prawej są coraz mniej znaczące. Ten schemat zapisu nazywamy standardem zapisywania dat ISO 8601standard ISO 8601ISO 8601.

Po przetworzeniu danych wejściowych możemy zająć się właściwym sortowaniem. Algorytm wykorzystuje dowolny stabilny algorytm sortujący, np. sortowanie bąbelkowe czy sortowanie przez zliczanie. Sortowanie jest pozycyjne i odbywa się od najmniej do najbardziej znaczącej pozycji.

W ten sposób uzyskujemy dane wejściowe dla kolejnych iteracji algorytmu, które będą się powtarzać, dopóki wszystkie cyfry w każdej liczbie nie zostaną rozpatrzone.

Zadanie 1. Jakub Jabłecznik i jego sad

Jakub Jabłecznik jest właścicielem sadu, w którym rosną jabłonie. Sad jest podzielony na trzy części – na każdej z nich rośnie inna odmiana jabłoni (ligol, gala lub lobo). Jakub odnotowuje sprzedaż jabłek w pliku sprzedaz.txt. Każdą transakcję zapisuje w oddzielnej linii - podaje w niej datę sprzedaży jabłek w formacie RRRR‑MM‑DD, ich odmianę w formie pełnej nazwy zapisanej wielkimi literami bez polskich znaków oraz masę w kilogramach. Poszczególne dane rozdziela za pomocą pojedynczej spacji. W roku 2021 Jakub sprzedał jabłka 12 razy (każdą z odmian dokładnie po cztery razy), wyłącznie we wrześniu i październiku.

Do zadania został dołączony plik tekstowy sprzedaz.txt, który składa się z $12$ linii. Odnotowano w nim sprzedaż jabłek - każda transakcja zapisana jest w pojedynczej linii zgodnie z formatem:

DATA_TRANSAKCJI GATUNEK_JABŁKA MASA_SPRZEDANYCH_JABŁEK

• DATA_TRANSAKCJI – to data zapisana w formacie RRRR‑MM‑DD

• GATUNEK_JABŁKA – to łańcuch znaków przechowujący jedną z trzech wartości: LIGOL, GALA bądź LOBO

• MASA_SPRZEDANYCH_JABŁEK – to dodatnia liczba naturalna

Przykładowe dane z pliku:

2021-09-08 LIGOL 2129
2021-10-02 LOBO 1265
2021-09-06 GALA 1327

Zadanie 1.1

Jakub nie prowadzi rejestru sprzedaży na bieżąco, przez co transakcje umieszczone w pliku nie są ułożone zgodnie z kolejnością, w jakiej faktycznie następowały. Napisz program, który posortuje transakcje od najwcześniejszej do najpóźniejszej. Wynik zapisz do pliku wynik1.txt.

Do oceny oddajesz:

• plik wynik1.txt z odpowiedzią (posortowane transakcje od najwcześniejszej do najpóźniejszej),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zgodnie z przedstawionymi założeniami udało nam się wczytać dane do tablic. Mamy do dyspozycji funkcję zamien, która pozwoli nam na zachowanie integralności danych.

Zadanie rozwiążemy, wykorzystując algorytm sortowania pozycyjnego dat. Zaczynając od najmniej znaczącej części daty (w tym wypadku cyfry jedności dnia), a kończąc na cyfrze tysięcy w roku, sortujemy stabilnie daty – cyfra po cyfrze.

Algorytm sortowania pozycyjnego dat wymaga stabilnego algorytmu sortującego. W implementacji wykorzystamy niezoptymalizowany algorytm sortowania bąbelkowegoPCfvfjgLksortowania bąbelkowego.

Deklarujemy funkcję sortowanieBabelkowe(indeks). Funkcja przyjmuje jeden parametr – indeks. Posłuży on nam do wskazania, którą cyfrę daty aktualnie przetwarzamy.

funkcja sortowanieBabelkowe(indeks)

Wewnątrz funkcji tworzymy dwie zagnieżdżone pętlę dla. Iterator pierwszej pętli (i) będzie przyjmował wartości od 1 do liczby elementów w tablicach minus 1, czyli 11. Z kolei iterator drugiej zagnieżdżonej pętli (j) będzie przyjmował wartości od 1 do liczby elementów w tablicach minus i, czyli kolejno do 11, 10, ..., 1. Operacja ta pozwoli na pominięcie dat ustawionych już na swoich pozycjach, jak również uniknięcie wyjścia poza zakres tablicy i błędnego działania programu.

funkcja sortowanieBabelkowe(indeks)
    dla i ← 1, 2, ..., długość(dataTransakcji) - 1 wykonuj:
        dla j ← 1, 2, ..., długość(dataTransakcji) - i wykonuj:

Wewnątrz zagnieżdżonej pętli porównujemy sąsiednie elementy wskazywane przez iterator j. Zawsze rozpatrujemy tę samą cyfrę daty, przekazaną do funkcji jako argument indeks. Pamiętajmy o konwersji znaku cyfry na liczbę całkowitą.

funkcja sortowanieBabelkowe(indeks)
    dla i ← 1, 2, ..., długość(dataTransakcji) - 1 wykonuj:
        dla j ← 1, 2, ..., długość(dataTransakcji) - i wykonuj:
        	jeżeli konwertujNaLiczbeCalkowita(dataTransakcji[j - 1][indeks]) > konwertujNaLiczbeCalkowita(dataTransakcji[j][indeks]) wykonuj:

Jeżeli aktualnie przetwarzana cyfra elementu dataTransakcji[j - 1] jest większa od cyfry elementu dataTransakcji[j], to zamieniamy je miejscami, wykorzystując wcześniej wspomnianą funkcję zamien.

funkcja sortowanieBabelkowe(indeks)
    dla i ← 1, 2, ..., długość(dataTransakcji) - 1 wykonuj:
        dla j ← 1, 2, ..., długość(dataTransakcji) - i wykonuj:
        	jeżeli konwertujNaLiczbeCalkowita(dataTransakcji[j - 1][indeks]) > konwertujNaLiczbeCalkowita(dataTransakcji[j][indeks]) wykonuj:
                zamien(j - 1, j)

Algorytm sortowania pozycyjnego dat wdrażamy poprzez przygotowanie pętli dla, której iterator będzie przyjmował kolejne wartości od 9 do 0 (po każdym przebiegu pętli wartość iteratora zostanie zmniejszona o 1). Wewnątrz pętli upewniamy się, że nie będziemy sortować symboli separujących części daty (kryją się pod indeksami 4 i 7) oraz uruchamiamy przygotowane sortowanie bąbelkowe.

Po zakończonym przebiegu pętli drukujemy informacje o każdej transakcji.

dla i ← 9 ... 0 wykonuj:
    jeżeli i = 4 LUB i = 7 wykonuj:
        kontynuuj
    
    sortowanieBabelkowe(i)

dla i ← 0 ... długość(dataTransakcji) - 1 wykonuj:
    wypisz(dataTransakcji[i])
    wypisz(gatunekJablka[i])
    wypisz(masa[i])

Poprawne wyniki dla danych w pliku sprzedaz.txt:

Zadanie 1.2

Napisz program, który wskaże, ile dni minęło między pierwszą a ostatnią transakcją dla każdego z gatunków jabłek. Wynik zapisz do pliku wynik2.txt.

Do oceny oddajesz:

• plik wynik2.txt z odpowiedzią (liczbami naturalnymi oznaczającymi, ile dni minęło między pierwszą a ostatnią transakcją dla każdego z gatunków jabłek),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zadanie można rozwiązać na wiele sposobów. Zaprezentowane tu rozwiązanie polega na posortowaniu transakcji według dat ich wykonania, a następnie wyszukaniu najwcześniejszej i najpóźniejszej sprzedaży dla każdego z gatunków jabłek. Na potrzeby rozwiązania załóżmy, że został wykonany kod z zadania 1.1 i dane zostały posortowane niemalejąco względem dat jako klucza.

Implementację rozwiązania zaczynamy od zadeklarowania funkcji obliczIleMinelo. Funkcja jako argument będzie przyjmować napis – gatunek jabłek.

funkcja obliczIleMinelo(gatunek)

Wewnątrz funkcji deklarujemy dwie zmienne pomocnicze: najwczesniejsza i najpozniejsza. Pierwsza z nich będzie przechowywać datę pierwszej sprzedaży, a druga – ostatniej.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

Tworzymy dwie pętle dla. Pierwsza z nich będzie wyszukiwać datę najwcześniejszej transakcji. W tym celu iterujemy po kolejnych elementach tablicy gatunekJablka. Jeśli łańcuch znaków przekazany jako argument do funkcji jest taki sam jak ten aktualnie przetwarzany w tablicy gatunekJablka, to zapisujemy do zmiennej najwczesniejsza datę sprzedaży odczytaną z tablicy dataTransakcji. Pamiętajmy, że zgodnie z przyjętymi założeniami tablice pod indeksem i zawsze przechowują komplet informacji o pojedynczej transakcji.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

    dla i ← 0, 1, ..., długość(gatunkiJablka) - 1 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najwczesniejsza ← dataTransakcji[i]
            przerwij

Podobną operację wykonamy, aby znaleźć ostatnią sprzedaż. Ponieważ transakcje zostały posortowane w kolejności od najwcześniejszej do najpóźniejszej, możemy przejść do końca po tablicy z gatunkami jabłek. Pierwsze dopasowanie będzie ostatnią sprzedażą wskazanego gatunku jabłek.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

    dla i ← 0, 1, ..., długość(gatunkiJablka) - 1 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najwczesniejsza ← dataTransakcji[i]
            przerwij

    dla i ← długość(gatunkiJablka) - 1, długość(gatunkiJablka) - 2, ..., 0 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najpozniejsza ← dataTransakcji[i]
            przerwij

Znaleźliśmy pierwszą i ostatnią sprzedaż przetwarzanego gatunku. Teraz skupimy się na policzeniu, ile dni minęło między transakcjami.

Tworzymy zmienną pomocniczą najwczesniejszaDzien. Daty zapisane są w formie napisów. Informacja o dniu znajduje się na pozycjach 8 i 9. Dokonujemy konwersji znaku w zmiennej najwczesniejsza, znajdującego się pod indeksem 8, na liczbę całkowitą. Mnożymy tę wartość przez 10 oraz dodajemy do niej przekonwertowany na liczbę całkowitą znak znajdujący się pod indeksem 9. Taką samą operację wykonujemy, tworząc zmienną najpozniejszaDzien, dane pobierając ze zmiennej najpozniejsza.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

    dla i ← 0, 1, ..., długość(gatunkiJablka) - 1 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najwczesniejsza ← dataTransakcji[i]
            przerwij

    dla i ← długość(gatunkiJablka) - 1, długość(gatunkiJablka) - 2, ..., 0 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najpozniejsza ← dataTransakcji[i]
            przerwij

    najwczesniejszaDzien ← konwertujNaLiczbeCalkowita(najwczesniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najwczesniejsza[9])
    najpozniejszaDzien ← konwertujNaLiczbeCalkowita(najpozniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najpozniejsza[9])

Sprawdzamy, czy obie transakcje odbyły się w tym samym miesiącu. W tym celu porównujemy znaki znajdujące się na pozycjach 5 i 6. Jeśli obie pary znaków są identyczne, odejmujemy od najpoznijeszyDzien wartość odczytaną ze zmiennej najwczesniejszyDzien. Jeżeli warunek jest nieprawdziwy, czyli transakcje miały miejsce w rożnych miesiącach, odejmujemy od $30$ (czyli liczby dni września) wartość zmiennej najwczesniejszyDzien oraz dodajemy wartość zmiennej najpozniejszyDzien.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

    dla i ← 0, 1, ..., długość(gatunkiJablka) - 1 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najwczesniejsza ← dataTransakcji[i]
            przerwij

    dla i ← długość(gatunkiJablka) - 1, długość(gatunkiJablka) - 2, ..., 0 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najpozniejsza ← dataTransakcji[i]
            przerwij

    najwczesniejszaDzien ← konwertujNaLiczbeCalkowita(najwczesniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najwczesniejsza[9])
    najpozniejszaDzien ← konwertujNaLiczbeCalkowita(najpozniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najpozniejsza[9])

    wynik ← 0

    jeżeli najwczesniejsza[5] = najpozniejsza[5] ORAZ najwczesniejsza[6] = najpozniejsza[6] wykonuj:
        wynik ← najpozniejszaDzien - najwczesniejszaDzien
    w przeciwnym przypadku wykonuj:
        wynik ← 30 - najwczesniejszaDzien + najpozniejszaDzien
   

Rozwiązanie zadania kończymy, drukując informacje na standardowym wyjściu oraz wywołując funkcję.

funkcja obliczIleMinelo(gatunek)
    najwczesniejsza ← ""
    najpozniejsza ← ""

    dla i ← 0, 1, ..., długość(gatunkiJablka) - 1 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najwczesniejsza ← dataTransakcji[i]
            przerwij

    dla i ← długość(gatunkiJablka) - 1, długość(gatunkiJablka) - 2, ..., 0 wykonuj:
        jeżeli gatunekJablka[i] = gatunek wykonuj:
            najpozniejsza ← dataTransakcji[i]
            przerwij

    najwczesniejszaDzien ← konwertujNaLiczbeCalkowita(najwczesniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najwczesniejsza[9])
    najpozniejszaDzien ← konwertujNaLiczbeCalkowita(najpozniejsza[8]) * 10 + konwertujNaLiczbeCalkowita(najpozniejsza[9])

    wynik ← 0

    jeżeli najwczesniejsza[5] = najpozniejsza[5] ORAZ najwczesniejsza[6] = najpozniejsza[6] wykonuj:
        wynik ← najpozniejszaDzien - najwczesniejszaDzien
    w przeciwnym przypadku wykonuj:
        wynik ← 30 - najwczesniejszaDzien + najpozniejszaDzien
    
    drukuj(gatunek + ": " + wynik)

gatunki ← ["LIGOL", "LOBO", "GALA"]

dla i ← 0 ... długość(gatunki)-1 wykonuj:
    obliczIleMinelo(gatunki[i])

Oto poprawny wynik zadania:

Słownik