Algorytm sortowania przez scalanie

Sortowanie przez scalanie polega na wielokrotnym dzieleniu na połowy tablicy zawierającej dane przeznaczone do uporządkowania.

Kiedy wszystkie tablice będą zawierać jeden element, następuje ich łączenie.

Dane pochodzące z dwóch tablic są zapisywane w ustalonym porządku (niemalejąco lub nierosnąco).

Proces łączenia tablic trwa do momentu, w którym pozostanie tylko jedna tablica.

Przykładowe zadanie typu maturalnego

Zadanie 1. Hodowla owiec

W miejscowości Rekursja działa farma zajmująca się hodowlą owiec. W gospodarstwie znajduje się 10 000 zwierząt. Każda owca jest oznaczona unikalnym numerem z zakresu (0, 100 000).

Zadanie 1.1

Co roku odbywa się strzyżenie owiec. Przeprowadzane jest przez dziesięć zespołów. Owce są prowadzone z pastwiska na miejsce strzyżenia w kolejności losowej: pierwsza przyprowadzona owca trafia do pierwszego zespołu, druga do drugiego; jedenasta owca znów do pierwszego zespołu i tak dalej. W ramach poszczególnych zespołów owce są strzyżone w kolejności zgodnej z ich oznaczeniami, zaczynając od najmniejszego numeru.

Napisz program, który przydzieli owce do poszczególnych zespołów oraz określi kolejność strzyżenia owiec w ramach zespołów.

W pliku owce.txt zapisano 10 000 liczb całkowitych z przedziału (0, 100 000), każdą w nowej linii – są to identyfikatory owiec; kolejność w pliku odzwierciedla kolejność, w której owce są sprowadzane z pastwiska na miejsce strzyżenia.

50270
51360
59263

Do oceny oddajesz:

• plik wyniki.txt zawierający odpowiedź (identyfikatory owiec podzielone na 10 grup zgodnie z treścią zadania, posortowane niemalejąco w obrębie grup; każda grupa powinna być oddzielona pojedynczą pustą linią)

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

Rozwiązanie przedstawimy w postaci pseudokodu, ponieważ na egzaminie maturalnym można korzystać z samodzielnie wybranego języka programowania: C++, Java lub Python.

Rozwiązanie

Na początek zauważmy, że opisany sposób podziału owiec pomiędzy zespoły zajmujące się strzyżeniem to nic innego jak przyporządkowanie na podstawie reszty z dzielenia przez 10. Nadajmy zespołom numery od 0 do 9. Uznajmy również, że będziemy numerować linie w pliku wejściowym od 0. Dzięki temu możemy powiedzieć, że wszystkie owce o identyfikatorach znajdujących się w liniach, których reszta z dzielenia przez 10 wynosi 0, powinny być strzyżone przez zespół o numerze 0. Wszystkie owce o identyfikatorach znajdujących się w liniach, których reszta z dzielenia przez 10 wynosi 1, powinny być strzyżone przez zespół o numerze 1 itd.

Zaczniemy pseudokod od wczytania pliku z danymi do dwuwymiarowej tablicy zespolyOwce. Tablica miała tyle tyle wierszy, ile jest zespołów (10) oraz tyle kolumn, ile wynosi liczba owiec n przez liczbę zespołów (czyli 1000). Zakładamy, że operator % to operator modulo (reszty z dzielenia), a operator // to dzielenie całkowitoliczbowe.

n = 10000
liczbaZespolow = 10
zespolyOwce[liczbaZespolow][n//liczbaZespolow]

dla i = 0, 1, ..., n - 1 wykonuj:
    zespol = i % liczbaZespolow
    miejsceWTtablicy = i // liczbaZespolow
    zespolyOwce[zespol][miejsceWTtablicy] = i-ty wiersz pliku "owce.txt"

Będziemy sortować tak przygotowane dane. Każdy wiersz tablicy zespolyOwce będziemy sortować oddzielnie z użyciem algorytmu sortowania przez scalanie.

dla i = 0, 1, ..., liczbaZespolow - 1 wykonuj:
    sortowanieScalanie(zespolyOwce[i], 1, n//liczbaZespolow)

Wewnątrz pętli wywołujemy funkcję realizującą algorytm sortowania przez scalanie. Jako dane wejściowe podajemy: tablicę z numerami owiec – czyli wiersz dwuwymiarowej tablicy, indeks komórkiindeks komórkiindeks komórki, od której rozpoczniemy sortowanie oraz indeks komórki, na której zakończymy sortowanie.

Gdy już wszystkie wiersze zostaną posortowane, pozostaje zapisać dane do pliku wyjściowego zgodnie z treścią zadania: kolejnymi grupami, a między każdą grupą powinien znaleźć się jeden pusty wiersz.

dla i = 0, 1, ..., liczbaZespolow - 1 wykonuj:
    dla j = 0, 1, ..., n//liczbaZespolow - 1 wykonuj:
        wypisz zespolyOwce[i][j] do pliku "wyniki.txt"
    wypisz pustą linię do pliku "wyniki.txt"

Przeanalizujmy algorytm sortujący.

funkcja sortowanieScalanie(owce[], lewy, prawy)
	jeżeli lewy >= prawy wykonaj:
    	zakończ
    środek = (lewy + prawy) // 2
	sortowanieScalanie(owce, lewy, środek)
    sortowanieScalanie(owce, środek + 1, prawy)
    scal(owce, lewy, środek, prawy)

1. Definujemy funkcję, która będzie dzielić tablicę na części. [linia 1]

2. Sprawdzamy, czy tablica, która ma zostać podzielona, nie jest tablicą jednoelementową (jeżeli tak jest, kończymy bieżące wywołanie rekurencyjnerekurencjarekurencyjne funkcji). [linie 2, 3]

3. Wyznaczamy środek podziału tablicy. [linia 4]

4. Wywołujemy funkcję sortowania przez scalanie dla utworzonych podtablic. [linie 5, 6]

5. Scalamy jednoelementowe tablice. [linia 7]

funkcja scal(owce[], lewy, środek, prawy)
	długośćL = środek - lewy
    długośćP = prawy - środek
    dla i = 1, 2, ... długośćL wykonuj:
    	lewaPom[i] = owce[lewy + i]
    dla i = 1, 2, ... długośćP wykonuj:
    	prawaPom[i] = owce[środek + i + 1]
    x = 1
    y = 1
    z = lewy
    dopóki (x < długośćL && y < długośćP) wykonuj:
    	jeżeli lewaPom[x] <= prawaPom[y] wykonaj:
        	owce[z] = lewaPom[x]
            x = x + 1
        jeżeli lewaPom[x] > prawaPom[y] wykonaj:
        	owce[z] = prawaPom[y]
            y = y + 1
        z = z + 1
	dopóki x < lewy wykonuj:
    	owce[z] = lewaPom[x]
        x = x + 1
        z = z + 1
	dopóki y < prawy wykonuj:
    	owce[z] = prawaPom[y]
        y = y + 1
        z = z + 1
	zakończ

1. Definiujemy funkcję scalania, która będzie zapisywać elementy pochodzące z dwóch podtablic w jednej tablicy z zachowaniem odpowiedniej kolejności. [linia 1]

2. Ustalamy długości podtablic, a następnie zapisujemy je w zmiennych pomocniczych. Musimy pamiętać, że podział jest umowny – nie tworzyliśmy nowych tablic danych, a zatem cały czas przetwarzamy tablicę Owce. Aby nie utracić danych z oryginalnej tablicy, musimy umieścić sortowaną część w tablicach pomocniczych. [linie od 2 do 7]

3. Tworzymy zmienne pomocnicze i ustawiamy ich wartość na 1 (w przedstawionym kodzie indeksy komórek tablicy zaczynają się od 1). [linie od 8 do 10]

4. Dopóki podtablice zawierają elementy, które nie znajdują się w scalonej tablicy, wykonywane są następne kroki. [linia 11]

5. Porównujemy kolejne wartości z podtablic i ustawiamy je w kolejności od najmniejszej do największej w pierwotnej tablicy. Wartość x inkrementujemyinkrementacjainkrementujemy po wpisaniu danych z tablicy lewaPom do pierwotnej tablicy. Tak samo postępujemy w przypadku wartości y (dla tablicy prawaPom). [linie od 11 do 17]

6. Inkrementujemy wartość zmiennej z, która przechowuje indeks komórki pierwotnej tablicy, do której powinniśmy wpisać dane. [linia kodu 18]

7. Jeżeli zdarzy się, że wyczerpiemy dane z jednej podtablicy, wpisujemy resztę danych z drugiej podtablicy do końca jej długości, a następnie kończymy działanie funkcji. [linie od 19 do 27]

Zadanie 1.2

Starsze owce przechodzą rutynowe badania kontrolne co 2 lata. Każdego roku jedna połowa owiec jest kierowana na badania. Druga połowa jest badana w kolejnym roku. W latach nieparzystych badania przechodzą tylko owce mające nieparzystą liczbę lat. Podobnie jest w przypadku lat parzystych i owiec mających parzystą liczbę lat. Owce badane są w kolejności od najstarszej do najmłodszej.

W 2012 roku przebadanych zostanie 2000 owiec.

Napisz program, który wyznaczy, w jakiej kolejności zwierzęta zostaną przebadane.

W pliku owce do badania.txt zapisano dane na temat wieku 2000 owiec. W każdej linii znajduje się liczba naturalna – wiek owcy w miesiącach.

Do oceny oddajesz:

• plik weterynarz.txt zawierający odpowiedź (oznaczenia owiec, zakwalifikowanych do badań w 2012 r.; kolejne wyniki zapisane w pliku powinny zgadzać się z kolejnością opisaną w zadaniu)

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

Rozwiązanie przedstawimy w postaci pseudokodu, ponieważ na egzaminie maturalnym można korzystać z samodzielnie wybranego języka programowania: C++, Java lub Python.

Rozwiązanie

owce[] = "owce do badania.txt"
długośćTablicy = 2000
owceDoBadania = doBadania(owce, długośćTablicy)
długośćTablicyOwceDoBadania = długość tablicy owceDoBadania
sortowanieScalanie(owceDoBadania, 1, długośćTablicyOwceDoBadania)
dla i = 0, 1, ... długośćTablicy - 1 wykonuj:
	wypisz owceDoBadania[i]

• Wywołujemy funkcję doBadania(), która zapisze interesujące nas dane w nowej tablicy owceDoBadania. [linia 3]

• Pozostałe operacje zapisane w głównej części kodu są takie same jak te z zadania 1.1.

funkcja doBadania(owce[], długośćTablicy)
	x = 1
	dla i = 0, 1, ... długośćTablicy - 1 wykonuj:
    	jeżeli ((owce[i] - (owce[i] % 12)) // 12) % 2 == 0 wykonaj:
        	owceDoBadania[x] = owce[i]
            x = x + 1
    zwróć owceDoBadania

1. Definiujemy funkcję, która zapisze dane spełniające warunki zadania w tablicy owceDoBadania. [linia 1]

2. Zapisujemy indeks komórki tablicy owceDoBadania, w której będą przechowywane kolejne dane [linia 2]

3. Odczytujemy kolejne komórki tablicy owce i wpisujemy do tablicy owceDoBadania te spośród nich, które odpowiadają parzystemu wiekowi zwierząt (liczonemu w latach). Aby ustalić wiek owcy z uwzględnieniem tylko skończonych lat (ignorując pozostałe miesiące), zaczynamy od wyznaczenia reszty z dzielenia wieku owcy podanego w miesiącach przez 12 (liczbę miesięcy, które nie składają się na pełne lata). Wynik odejmujemy od wieku liczonego w miesiącach i dzielimy przez 12, aby wyznaczyć wiek w latach. Następnie sprawdzamy, czy jest on parzysty. [linia 4]

4. Jeżeli wiek jest parzysty, wpisujemy go do tablicy owceDoBadania i inkrementujemy wartość x (wskazujemy indeks następnej komórki). [linie 5, 6]

sortowanieScalanie(owceDoBadania[], lewy, prawy)
	jeżeli lewy >= prawy wykonaj:
    	zakończ
    środek = (lewy + prawy) // 2
	sortowanieScalanie(owceDoBadania, lewy, środek)
    sortowanieScalanie(owceDoBadania, środek + 1, prawy)
    scal(owceDoBadania, lewy, środek, prawy)

• Definicja funkcji sortowanieScalanie() jest taka sama jak zadaniu 1.1.

scal(owceDoBadania[], lewy, środek, prawy)
	długośćL = środek - lewy
    długośćP = prawy - środek
    dla i = 1, 2, ... długośćL wykonuj:
    	lewaPom[i] = owceDoBadania[lewy + i]
    dla i = 1, 2, ... długośćP wykonuj:
    	prawaPom[i] = owceDoBadania[środek + i + 1]
    x = 1
    y = 1
    z = 1
    dopóki (x < długośćL && y < długośćP) wykonuj:
    	jeżeli lewaPom[x] >= prawaPom[y] wykonaj:
        	owceDoBadania[z] = lewaPom[x]
            x = x + 1
        jeżeli lewaPom[x] < prawaPom[y] wykonaj:
        	owceDoBadania[z] = prawaPom[y]
            y = y + 1
        z = z + 1
	dopóki x < lewy wykonuj:
    	owceDoBadania[z] = lewaPom[x]
        x = x + 1
        z = z + 1
	dopóki y < prawy wykonuj:
    	owceDoBadania[z] = prawaPom[y]
        y = y + 1
        z = z + 1
	zakończ

• Modyfikujemy funkcję scal() tak, aby zapisywała ona wartości od największej do najmniejszej. Zamieniamy w tym celu znaki mniejszości ($<$) na znaki większości ($>$) i odwrotnie. [linie 12, 15]

Słownik