Algorytm sortowania pozycyjnego słów

Sortowanie pozycyjne polega na ustaleniu kolejności słów według pozycji występujących w nich kolejnych liter.

Działanie sortowania pozycyjnego opiera się na porównywaniu słów względem znaków w ciągu, gdzie i‑ty znak słowa jest zawsze porównywany z i‑tym znakiem innego słowa.

Po ustaleniu, według której pozycji liter nastąpi sortowanie, słowa są ustawiane w odpowiedniej kolejności za pomocą dowolnego stabilnego algorytmu sortowania (jak sortowanie bąbelkowe, przez wstawianie, przez zliczanie).

Jeżeli słowo A jest sufiksem słowa B i słowo B jest dłuższe, to słowo A jest mniejsze w porządku leksykograficznym.

Jes to równoznaczne z: AAB < AABA

Złożoność obliczeniowa algorytmu wynosi O(d(n + k)), gdzie d oznacza liczbę znaków w słowach, n – liczbę słów, natomiast k – liczbę znaków, z których dane słowa się składają.

Powyższa złożoność obliczeniowa oznacza, że dla małego zakresu różnych znaków algorytm sortowania pozycyjnego jest efektywniejszy niż algorytmy bardziej złożone, stosujące metodę „dziel i zwyciężaj”, których średnia złożoność obliczeniowa wynosi O(nlogn).

Aby posortować słowa, trzeba ustalić, w jakim porządku powinny być one zapisywane. Uniwersalnym wyborem jest porządek leksykograficznyporządek leksykograficznyporządek leksykograficzny, stosowany powszechnie w słownikach, encyklopediach, indeksach itp.

Zadanie 1. Herbaciarnia

W herbaciarni „Kompilator” stale powstają nowe mieszanki herbaty.

Pan Proceduralny zajmuje się przygotowywaniem odpowiednich kompozycji z suszonych liści oraz aromatycznych dodatków.

Ma on tajemny sposób na przechowywanie składników – trzyma je w kolejności leksykograficznej według trzech ostatnich liter każdego słowa.

Zadanie 1.1

Ktoś zamienił miejscami słoiki, przez co Pan Proceduralny nie może przygotować mieszanki według powierzonego mu przepisu.

Napisz program, który wypisze kolejność, w jakiej powinny znajdować się słoiki ze składnikami. Wyniki zapisz do pliku wyniki.txt.

Plik Lista składników.txt zawiera 28 nazw składników wykorzystywanych w herbaciarni, każda zapisana jest w nowej linii.

Lista składników.txt

Fragment przykładowych danych:

MATCH
OOLON
SENCH

Do oceny oddajesz:

• plik wynik.txt zawierający odpowiedź (nazwy składników uporządkowane w kolejności leksykograficznej według trzech ostatnich liter każdego słowa)

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

Rozwiązanie

pozycja = długośćCiąguZnaków - 1
pozycjaKońcowa = długośćCiąguZnaków - 3
dopóki pozycja >= pozycjaKońcowa wykonuj:
	sortuj(lista[], długośćListy, pozycja)
    pozycja = pozycja - 1
wypisz lista do pliku

1. Zapisujemy pierwszą pozycję (literę), którą będziemy sprawdzać. Z kolei do zmiennej pozycjaKońcowa zapisujemy indeks pozycji, na której zaczyna się podciąg, który bierze udział w sortowaniu. [linia 1]

2. Tworzymy pętlę. Zapisane wewnątrz niej instrukcje będą wykonywane dopóty, dopóki nie zostanie przekroczona długość podciągu, według którego chcemy dokonać sortowania ciągu znaków opisującego składnik mieszanki. [linia 3]

3. Sortujemy listę składników, biorąc pod uwagę literę na odpowiedniej pozycji. Następnie dekrementujemydekrementacjadekrementujemy zmienną, w której zapisana jest obecna pozycja, aby użyć jej w następnym cyklu pętli. [linie 4, 5]

4. Wypisujemy posortowaną listę składników. [linia 6]

funkcja sortuj(lista, długośćListy, pozycja)
	lista2[długośćListy]
    liczbaZnakówWAlfabecie = 26
	pomocnicza[liczbaZnakówWAlfabecie]
    dla i = 0, 1, ... długośćListy - 1 wykonuj:
        pomocnicza[i] = 0
	dla i = 0, 1, ... długośćListy - 1 wykonuj:
    	pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] = pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] + 1
	dla i = 1, 2, ... liczbaZnakówWAlfabecie - 1 wykonuj:
    	pomocnicza[i] = pomocnicza[i] + pomocnicza[i-1]
    dla i = długośćListy - 1, długośćListy - 2, ... 0 wykonuj:
    	lista2[pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)]] = lista[i]
        pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] = pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] - 1
    lista = lista2

1. Deklarujemy funkcję, która będzie sortować znaki znajdujące się na ustalonej wcześniej pozycji. [linia 1]

2. Do tablicy pomocniczej wpisujemy same zera. Jest to konieczne do późniejszego zliczania znaków. [linia 4, 5, 6]

3. Tworzymy pętlę. W każdym jej cyklu zliczone zostaną elementy należące do wybranego zakresu. Ponieważ sortujemy słowa, zakresem będzie lista znaków w alfabecie (policzymy wystąpienia liter A, B, C itd.). Rezultaty zapiszemy, zwiększając wartości o do której interesuje nas sortowanie odpowiednich komórekkomórka tablicykomórek w tablicy pomocniczej. Od wartości znaku (zapisanej jako odpowiadający mu kod ASCIIkod ASCIIkod ASCII) odejmujemy wartość liczbową odpowiadającą znakowi A. [linie 7, 8]

4. Zmieniamy sposób zapisywania danych w tablicy pomocniczej. Zamiast liczby wystąpień litery znajdującej się na odpowiedniej pozycji w alfabecie, komórka będzie zawierać również liczbę znaków, które znajdują się na wcześniejszej pozycji. W celu wprowadzenia zmian dodajemy do wartości komórki w tablicy pomocniczej wartość zapisaną w poprzedniej komórce. [linie 9, 10]

5. Tworzymy listę zawierającą znaki na pozycjach, które określa tablica pomocnicza. Po umieszczeniu znaku na odpowiedniej pozycji dekrementujemydekrementacjadekrementujemy wartość w tablicy pomocniczej (jeśli tego nie zrobimy, sortowanie nie zadziała dla znaków, które pojawiają się więcej niż jeden raz). [linie 11, 12, 13]

6. Umieszczamy posortowaną tablicę w liście wynikowej, czym kończymy pojedynczy cykl sortowania. [linia 14]

Odpowiedź

Odpowiedź do zadania dla danych zapisanych w pliku Lista składników.txt:

Zadanie 1.2

Po dodaniu dwóch nowych składników właściciel herbaciarni zauważył, że najczęściej używane składniki znajdują się na końcu magazynu. Ustalono więc, że słoiki ze składnikami powinny być ustawione w odwrotnym porządku alfabetycznym – wciąż jednak uwzględniając jedynie trzy ostatnie litery każdego słowa. Poproszono również, aby dla ułatwienia zapisać numery miejsc nowych składników wraz z ich nazwami.

Na jakich pozycjach powinny się znaleźć nowe składniki?

Korzystając z wybranego języka, napisz program, który posortuje dane w odwrotnej kolejności alfabetycznej, a następnie wypisze numery pozycji dwóch nowych składników oraz ich nazwy (znajdują się one na dwóch ostatnich pozycjach na liście). Wyniki zapisz do pliku wyniki.txt.

Plik Lista składników.txt zawiera 28 nazw składników wykorzystywanych w herbaciarni, każda zapisana jest w nowej linii.

Fragment przykładowych danych:

PUERH
MATCH
OOLON
SENCH
PEKOE

Do oceny oddajesz:

• plik wynik.txt zawierający odpowiedź (nazwy składników uporządkowane w odwrotnej kolejności leksykograficznej według trzech ostatnich liter każdego słowa; powinien również zawierać oddzielone pojedynczą pustą linią od posortowanej listy nazwy wyróżnionych składników wraz z pozycjami)

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

Rozwiązanie

Skorzystajmy z nieco zmodyfikowanego kodu z podpunktu 1. i zapiszmy przed sortowaniem słowa, których pozycję należy podać jako rozwiązanie zadania.

Podobnie jak w podpunkcie 1., do uporządkowania zbioru wykorzystamy algorytm sortowania przez zliczanie.

Algorytm ten nie jest jednak przystosowany do użycia w celu porządkowania zbioru słów w kolejności odwrotnej od alfabetycznej. Aby znaki zostały umieszczone na właściwych pozycjach, musimy w ostatnim kroku [linia 9] zmodyfikować sposób uzupełniania listy wynikowej o tablicę posortowaną.

Na końcu należy znaleźć nowe nazwy i podać je wraz z numerami pozycji na liście.

szukaneSłowa[0] = lista[28]
szukaneSłowa[1] = lista[29]

pozycja = długośćCiąguZnaków - 1
pozycjaKońcowa = długośćCiąguZnaków - 3
dopóki pozycja >= pozycjaKońcowa wykonuj:
	sortuj(lista[], długośćListy, pozycja)
    pozycja = pozycja - 1

dla i = 0, 1, ... długośćListy wykonuj:
    jeżeli lista[i] == szukaneSłowa[0] wykonaj:
        pozycja[0] = i
    jeżeli lista[i] == szukaneSłowa[1] wykonaj:
        pozycja[1] = i

wypisz lista do pliku
wypisz pustą linię do pliku
wypisz szukaneSłowa[0] pozycja[0] do pliku
wypisz szukaneSłowa[1] pozycja[1] do pliku

• Zapisujemy nazwy szukanych składników [linie 1, 2]. Przeszukujemy listę, aby znaleźć pozycje szukanych słów [linie od 10 do 14].

• Wypisujemy nazwy nowych składników wraz z ich pozycjami na liście [linie od 16 do 19].

funkcja sortuj(lista, długośćListy, pozycja)
	lista2[długośćListy]
    liczbaZnakówWAlfabecie = 26
	pomocnicza[liczbaZnakówWAlfabecie]
    dla i = 0, 1, ... długośćListy - 1 wykonuj:
        pomocnicza[i] = 0
	dla i = 0, 1, ... długośćListy - 1 wykonuj:
    	pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] = pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] + 1
	dla i = 1, 2, ... liczbaZnakówWAlfabecie - 1 wykonuj:
    	pomocnicza[i] = pomocnicza[i] + pomocnicza[i-1]
    dla i = długośćListy - 1, długośćListy - 2, ... 0 wykonuj:
    	lista2[pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)]] = lista[i]
        pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] = pomocnicza[kodASCII(lista[i][pozycja]) - kodASCII(A)] - 1
    dla i = 0, 1, ... długośćListy - 1 wykonuj:
        lista[i] = lista2[długośćListy - i - 1]

• Uruchamiamy pętlę, w której będziemy odwracać kolejność słów zapisanych na posortowanej liście (ostatnie słowo trafi teraz na pierwszą pozycję, przedostatnie na drugą itd.) [linie 14, 15].

Komentarz do zadania

Rozwiązując przedstawione zadania, możesz użyć innego algorytmu sortowania. Musisz jednak pamiętać, aby zastosować stabilny algorytm sortowaniastabilność algorytmu sortowaniastabilny algorytm sortowania.

Odpowiedź

Odpowiedź do zadania dla danych zapisanych w pliku Lista składników.txt:

Słownik