Paradoks? Przecież sortownie, to porządkowanie jakiegoś zbioru, a rozrzucanie kojarzy się z czymś przeciwnym. Niekoniecznie. Rozrzucać też możemy w sposób systematyczny!

Rozważmy następującą sytuację. Po skończonym egzaminie, w którym brało udział 125 studentów, nauczyciel wraca ze stosem prac egzaminacyjnych ułożonych w sposób przypadkowy. Prace należy sprawdzić i utworzyć alfabetyczną listę studentów wraz z ich ocenami.  Algorytmy takie jak MergeSort, czy QuickSort nie wchodzą w grę. Zbyt skomplikowane, by mógł je wykonać bezbłędnie człowiek dla tak dużych danych. Algorytm SelectionSort, chociaż prosty, zniechęci każdego dużą liczbą porównań i kłopotami technicznymi związanymi z przeglądaniem pliku 125, potem 124 itd. prac. Sądzę, że większość z Państwa wpadnie na pomysł, by najpierw przeprowadzić wstępne "uporządkowanie" np. grupując prace ze względu na pierwszą literę nazwiska. Wystarczy do tego dostatecznie duży stół i jednokrotne przejrzenie wszystkich prac. To jest właśnie "rozrzucanie". Teraz wystarczy uporządkować prace w każdym z małych, jak należy się spodziewać, plików, by otrzymać posortowany alfabetycznie zbiór prac.

Możemy też postąpić nieco inaczej. Jeżeli każda praca, oprócz nazwiska, jest opatrzona czterocyfrowym numerem indeksu autora, to podzielmy prace na  10 grup, ze względu na pierwszą cyfrę numeru indeksu. Wprawdzie utworzone grupy zawierają teraz więcej elementów niż w poprzedniej metodzie, ale wszystkie razem zajmują dużo mniej miejsca.  Teraz każdą grupę prac możemy uporządkować osobno stosując, np. algorytm InsertionSort.

Algorytmy, o których będzie mowa w dalszej części tego wykładu stosują różne wersje operacji rozrzucania. Dzięki temu ich koszt okaże się liniowy ze względu na liczbę elementów. Niestety, podstawową wadą tych algorytmów są dodatkowe założenia, które muszą spełniać dane. Algorytmy sortujące w modelu drzew decyzyjnych, takie jak QuickSort, czy InsertionSort, mogły być stosowane dla dowolnych danych, ale za to ich koszt był w najlepszym razie liniowo logarytmiczny.

Pytanie 4. Wyobraźmy sobie rekurencyjną wersję procesu sortowania prac studenckich, polegającą na tym, że po pierwszym rozrzuceniu, każdą grupkę prac (nazwiska autorów każdej z nich zaczynają się na tę samą literę) sortujemy rozrzucając znów wszystkie prace na kupki ze względu na drugą literę nazwiska. Na koniec, gdy każda praca leży osobno, łączymy je w jeden ciąg. Ile miejsca zajęłoby nam posortowanie 125 prac, jeżeli prace są napisane na kartkach typu A4 (ok. 20 centymetrów szerokości)?

« poprzedni punkt

następny punkt »