Algorytm sortowania szybkiego

Sortowanie szybkie polega na wybraniu elementu rozdzielającego (tzw. pivotpivotpivot) oraz podzieleniu tablicy zawierającej dane na dwie części. W jednej zostają umieszczone elementy o wartościach większych niż pivot, w drugiej zaś — elementy o wartościach od niego mniejszych. Następnie elementy mniejsze i większe sortowane są osobno według tej samej zasady. Sortowanie odbywa się rekurencyjnierekurencjarekurencyjnie do momentu, gdy każda z podtablic zostanie uporządkowana. Dokładne omówienie algorytmu sortowania szybkiego zostało przedstawione w e‑materiale Sortowanie szybkiePpzx1YyemSortowanie szybkie.

Zadanie 1. Wystawa obrazów

W pewnym muzeum organizowana jest wystawa obrazów poświęconych figurom geometrycznym. Okoliczne muzea wypożyczyły placówce części własnych ekspozycji pasujących do tematyki wystawy.

Zadanie 1.1

Muzeum chce ustalić, w którym roku powstało najwięcej dzieł z obecnej wystawy. Obrazy te zostaną oprawione w złote ramy.

Plik lata.txt zawiera 76 wierszy zawierających rok powstania poszczególnych obrazów pokazywanych na wystawie (każdy rok zapisano w osobnym wierszu).

Napisz program, który wyznaczy rok, z którego pochodzi najwięcej dzieł, oraz wskaże, ile złotych ram na obrazy z tego roku powinno przygotować muzeum. Przyjmij, że jest tylko jeden rok z maksymalną liczbą powstałych dzieł. Zapisz obie wartości do pliku ramy.txt.

Do oceny oddajesz:

• plik ramy.txt zawierający odpowiedź (rok, w którym powstało najwięcej prezentowanych obrazów, oraz liczbę złotych ram potrzebnych do ich oprawienia)

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

Rozwiązanie

W celu łatwiejszego zliczenia obrazów pochodzących z danego roku, posortujemy dane z pliku. Użyjemy do tego algorytmu sortowania szybkiego.

funkcja sortowanie_szybkie(Lata[], lewy, prawy)
	jeżeli lewy < prawy:
		punkt_podziału ← podział(Lata, lewy, prawy)
		sortowanie_szybkie(Lata, lewy, punkt_podziału - 1)
		sortowanie_szybkie(Lata, punkt_podziału + 1, prawy)

1. Definiujemy funkcję, która będzie dzielić tablicę na dwie części, a następnie sortować je osobno. [linia 1]

2. Sprawdzamy, czy tablica, którą mamy podzielić, nie jest jednoelementowa (jeżeli jest, indeksyindeks komórkiindeksy lewy i prawy są sobie równe). [linia 2]

3. Wyznaczamy punkt podziału (pivot); jednocześnie zapisujemy dane w tablicy z uwzględnieniem punktu podziału. [linia 3]

4. Rekurencyjnie uruchamiamy funkcję podziału dla utworzonych podtablic. [linie 4, 5]

funkcja podział(Lata[], lewy, prawy)
	pivot ← Lata[prawy]
	mniejsza ← lewy - 1
	dla większa = lewy, lewy + 1, ... prawy - 1 wykonuj:
		jeżeli Lata[większa] < pivot:
			mniejsza ← mniejsza + 1
			zamień Lata[mniejsza] z Lata[większa]
	zamień Lata[mniejsza + 1] z Lata[prawy]
	zwróć (mniejsza + 1)

1. Definiujemy funkcję podziału, która będzie ustawiać wartości mniejsze niż pivot po lewej stronie tablicy, zaś wartości większe - po prawej; następnie funkcja zwróci pozycję wartości rozdzielającej tablicę. [linia 1]

2. Ustawiamy pozycję elementu rozdzielającego oraz wartość zmiennej mniejsza. Pamiętajmy o tym, że przed zamianą pozycji komórek (w linii 7) dokonujemy inkrementacjiinkrementacjainkrementacji wartości zmiennej mniejsza, a zatem musimy nadać jej wartość o 1 mniejszą od pierwszej sprawdzanej pozycji. [linie 2, 3]

3. Inicjujemy pętlę, w której wartość większa będzie odpowiadać kolejnym indeksom tabeli. [linia 4]

4. Sprawdzamy w każdej iteracji pętliiteracja pętliiteracji pętli, czy wartość w tablicy dla indeksu większa ma wartość mniejszą niż pivot. Jeżeli tak, inkrementujemy wartość zmiennej mniejsza, a następnie zamieniamy miejscami komórkikomórka tablicykomórki o indeksach większa i mniejsza. [linie od 5 do 7]

5. Wstawiamy pivot w odpowiednie miejsce w tablicy — tak, by wszystkie elementy po lewej stronie były od niego mniejsze, a wszystkie po prawej — większe. [linia 8]

6. Zwracamy pozycję pivota i kończymy działanie funkcji. [linia 9]

Przejdźmy do właściwej części zadania. Na początku wczytujemy i sortujemy dane. Następnie zapisujemy algorytm, który przeszukuje posortowaną tablicę, by znaleźć rok powstania największej liczby obrazów oraz wskazać liczbę potrzebnych do ich oprawienia złotych ram:

Lata[0..75] ← wczytaj dane z pliku "lata.txt"
sortowanie_szybkie(Lata, 0, długość(Lata) - 1)

rok ← Lata[0]
liczba ← 1
maks_rok ← rok
maks_liczba ← 1

dla i = 1, 2, ..., długość(Lata) - 1 wykonuj:
	jeżeli Lata[i] = rok:
		liczba ← liczba + 1
	w przeciwnym razie:
		rok ← Lata[i]
		liczba ← 1

	jeżeli liczba >= maks_liczba:
		maks_liczba ← liczba
		maks_rok ← rok

zapisz maks_rok maks_liczba do pliku "ramy.txt"

1. Wczytujemy dane z pliku. [linia 1]

2. Wywołujemy funkcję, w której został zaimplementowany algorytm sortowania szybkiego. Jako dane wejściowe podajemy: tablicę lat, pozycję, od której należy rozpocząć sortowanie, oraz pozycję końcową. Tablice indeksujemy od zera, zgodnie z ich reprezentacją w komputerze. [linia 2]

3. Deklarujemy potrzebne zmienne. [linie 4‑7]

4. Korzystając z pętli, sprawdzamy poniższe warunki dla każdego roku:

   • jeżeli jest taki sam jak poprzednio rozpatrywany, dodajemy jedno wystąpienie do licznika wystąpień; [linia 11]

   • jeżeli jest inny niż poprzednio rozpatrywany, zapisujemy nowy rok jako aktualnie rozpatrywany i ustawiamy licznik wystąpień na 1. [linie 13‑14]

5. Z każdą iteracją pętli sprawdzamy również, czy dany rok pojawia się najwięcej razy. Jeżeli tak, zapisujemy ten rok i liczbę jego wystąpień w odpowiednich zmiennych. [linie 16‑18]

6. Na koniec zapisujemy wyniki do odpowiedniego pliku. [linie 20‑21]

Zadanie 1.2

Po zakończeniu wystawy trzeba przygotować eksponaty do zwrócenia muzeom, z których zostały wypożyczone. Sporządzono w tym celu listę — numer każdego jej wiersza oznacza pozycję obrazu na wystawie, zaś w wierszu zapisany jest sześciocyfrowy kod z oznaczeniem danego muzeum i obrazu:

• cyfry na pozycjach od $1.$ do $3.$ (od lewej strony) oznaczają numer muzeum,

• cyfry na pozycjach od $4.$ do $6.$ to oznaczenie obrazu w danym muzeum.

Im większa jest liczba stanowiąca numer muzeum, tym dalej się ono znajduje. Obrazy należy ułożyć w takiej kolejności, aby najpierw zostały wysłane dzieła należące do najbardziej odległych muzeów. W rezultacie wszystkie eksponaty wrócą na swoje miejsce w podobnym czasie. Przyjmijmy, że z każdego muzeum wypożyczono tylko jeden obraz.

Plik lista.txt zawiera 76 liczb (każda zapisana w osobnym wierszu), stanowiących numery poszczególnych dzieł. Numery te się nie powtarzają.

Napisz program, który uporządkuje obrazy w kolejności ich wysyłki oraz zapisze numery muzeów, do których wysyłane są obrazy, w pliku kolejność.txt.

114165
158168
130185
125172

158
130
125
114

Do oceny oddajesz:

• plik kolejność.txt zawierający odpowiedź (liczby całkowite dodatnie będące numerami muzeów w odpowiedniej kolejności)

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

Rozwiązanie

Aby rozwiązać zadanie, musimy nieco zmienić kod, który przedstawiliśmy w podpunkcie 1.

W celu zmiany porządku sortowania na nierosnący należy zmodyfikować funkcję podział(), ponieważ to ona odpowiada za dzielenie elementów na podtablice mniejszych i większych elementów.

funkcja podział(Kod[], lewy, prawy)
	pivot ← Kod[prawy]
	mniejsza ← lewy - 1
	dla większa = lewy, lewy + 1, ... prawy - 1 wykonuj:
		jeżeli Kod[większa] > pivot:
			mniejsza ← mniejsza + 1
			zamień(Kod[mniejsza], Kod[większa])
	zamień(Kod[mniejsza + 1], Kod[prawy])
	zwróć (mniejsza + 1)

• Modyfikujemy wyrażenie warunkowe; sprawdzamy, czy liczba na pozycji wskazywanej przez indeks większa jest większa niż element rozdzielający. Jeżeli tak, postępujemy dalej tak samo jak w poprzednim zadaniu. [linia 5]

Po posortowaniu musimy dodatkowo umieścić trzy pierwsze cyfry każdego kodu w tablicy pomocniczej, którą zapiszemy w pliku kolejność.txt.

Kod[0..75] ← wczytaj dane z pliku "lista.txt"
sortowanie_szybkie(Kod, 0, długość(Kod) - 1)

Pomocnicza[0..długość(Kod)-1]
dla i = 0, 1, ..., długość(Kod) - 1 wykonuj:
	Pomocnicza[i] ← kod_muzeum(Kod[i])

zapisz Pomocnicza[0..długość(Kod)-1] do pliku "kolejność.txt"

• Po posortowaniu danych z pliku lista.txt umieszczamy kod każdego muzeum w tablicy pomocniczej. Korzystamy w tym celu z pomocniczej funkcji kod_muzuem() zdefiniowanej poniżej. [linie 4, 5, 6]

• Zapisujemy kody poszczególnych muzeów w pliku kolejność.txt i kończymy działanie programu. [linia 8]

funkcja kod_muzeum(kod)
	kod ← kod div 1000
	zwróć kod

1. Definiujemy funkcję, która będzie przekształcać sześciocyfrowy kod w liczbę trzycyfrową, złożoną z trzech pierwszych cyfr kodu. [linia 1]

2. Kod dzielimy całkowicie przez tysiąc — pozbywamy się w ten sposób trzech ostatnich cyfr (pozostaje liczba trzycyfrowa). [linia 2]

3. Zwracamy wartość zmiennej kod. [linia 3]

sort(tab, tab + n)

Arrays.sort(tab)

sorted(tab)

Słownik