85 (147)

Rozdział 4. • Zagadnienia trudniejsze 121

Początek i koniec programu (czyli wpisanie i wypisanie danych) jest jasny i nie wymaga komentarza. Warto jedynie zwrócić uwagę, że liczba uczniów została określona jako stała i w dalszej części programu posługujemy się nią, podając jej nazwę (także w deklaracji tablicy). Nie można by się, co prawda, posłużyć wczytaną przez użytkownika zmienną (tablica musi mieć wartość określoną już w momencie kompilacji), ale zmiana liczebności grupy osób wymaga jedynie poprawienia wartości tej stałej przed kompilacją programu. Można by także zadeklarować tablicę dużego rozmiaru, zmienną określającą liczbę osób, wczytać ją (i sprawdzić, czy jest mniejsza niż rozmiar tablicy) i operować jedynie na części tablicy. Spróbuj przerobić program tak, by to zrealizować.

Wyjaśnienia wymaga procedura sortowania. Posłużyliśmy się inną metodą, niż poznane w ćwiczeniu 4.3 sortowanie bąbelkowe. Idea tej metody jest bardzo prosta: wybieramy pierwszy element tabeli i przegrupowujemy ją tak, żeby wszystkie mniejsze od niego znalazły się po jego lewej, a większe lub równe po prawej stronie. Następnie rekurencyjnie sortujemy w identyczny sposób lewą i prawą stronę tej tabeli. Sortowanie wykonujemy do momentu, kiedy w sortowanym kawałku mamy przynajmniej dwa elementy.

Spróbuj prześledzić działanie takiego algorytmu na kartce, dla małego zbioru liczb. Jako przykład niech posłuży Ci poniższa ilustracja, ilustrująca sortowanie 8 elementów: 8, 4, 17, 3, 16, 5, 1, 21.

	4	17	3	16	5	1	21
4] Ulż	3	5		$		16	21

0 CD	21
CD ®	21

H303 ® [UD 03 ®

1

3

4

5

8

16

17

21

Ten algorytm sortowania (ąuicksort), nie dość że prosty w zapisie, jest jeszcze bardzo efektywny. Średnia liczba wykonywanych przez niego operacji jest rządu N*logN, podczas gdy dla sortowania bąbelkowego był to rząd N². Oczywiście dla piętnastoosobowej grupy nie zaobserwujesz różnicy w czasie działania. Gdybyś jednak musiał posortować dane dotyczącej dużej grupy osób, byłoby to znaczące. Sprawdź, jak zmieniają się wartości N² oraz N*logN w zależności od liczby N.