POLSKI SPOJ

Witajcie! Jest to kolejny z serii tutoriali uczący Pythona, a w przyszłości być może nawet Cythona i Numby. Jeśli chcesz nauczyć się nowych, zaawansowanych konstrukcji to spróbuj rozwiązać kilka następnych zadań. Powodzenia! 

Zadanie

Sortowanie jest fundamentalnym problemem w informatyce. W tym zadaniu nauczysz się prostej metody sortowania. Co więcej, w kolejnym zadaniu będziesz testować wadliwe implementacje sortowania. Motywem przewodnim w kolejnych kilku zadaniach jest testowanie prostych ale błędnych implementacji algorytmów. Najpierw nauczysz się jak rozwiązać dany problem, a później będziesz testował rozwiązania innych.

Najpierw proste wyjaśnienie w jaki sposób odbywa się sortowanie:

1. Początkowe dzielenie

Na początku posiadamy listę bliżej nieokreślonych elementów. Elementy nie mają żadnego porządku. Kolejny etap będzie potrzebował uporządkowanych list. Zastosujemy więc prosty zabieg: stworzymy listę pojedynczych elementów. Dla przykładu:

2. Scalanie 

Dwie uporządkowane listy możemy scalić w jedną, także uporządkowaną. Zasada jest prosta: Wybieramy mniejszy element na początku obu list, wyjmujemy go i przenosimy na koniec wynikowej listy. Dla przykładu:

3. Podziel i zwyciężaj

Powyższe dwie metody wykorzystamy do zaimplementowania sortowania. Na początku, dzielimy początkową listę na listę pojedynczych elementów. Następnie parami scalamy listy. Powstanie w ten sposób dwa razy mniej list o dwa razy więcej elementach. Ponownie scalamy parami listy. Ponownie, powstanie dwa razy mniej list. Na samym końcu pozostanie tylko jedna lista. Dla przykładu:

4. Testowanie

Twoim zadaniem jest zaimplementować funkcje o nazwach divide, merge i sorting. Pobierz szablon kodu, po uzupełnieniu odeślij jako zgłoszenie. Szablon zawiera doklejony kod, który sam pobierze dane wejściowe i wypisze dane wyjściowe. Musisz jedynie zaimplementować trzy metody.

Przykładowe dane oraz wyniki są dostępne do pobrania.