ALG 0

90 Rozdział 4. Algorytmy sortowania

Rys. 4 - 8.

Sortowanie metodą Ouickson na przykładzie.

Tutaj zapowiem jedynie, że chodzi o taką dekompozycję problemu, aby uzyskać zysk czasowy' wykonywania programu (jak i przy okazji uproszczenie rozwiązywanego zadania). Algorytm Owcksort spełnia te oba założenia wręcz wzorcowo!

4.4. Uwagi praktyczne

Kryteria wyboru algorytmu sortowania mogą być zebrane w kilka łatwych do zapamiętania zasad:

• do sortowania małych ilości elementów nie używaj superszybkich algorytmów, takich jak np. Quicksort, gdyż zysk będzie znikomy;

• część znanych z literatury' i prasy fachowej algorytmów sortowania nie jest nigdy - lub jest bardzo rzadko - stosowana praktycznie. Powód jest dość prosty: trzymając się dobrze znanych metod mamy większą pewność, iż nie popełnimy jakiegoś nadprogramowego błędu.

Podczas programowania warto również uważnie czytać, czy' w bibliotekach standardowych używanego kompilatora nie ma już zaimplementowanej funkcji sortującej. Przykładowo w kompilatorze gcc istnieje gotowa funkcja o nazwie... t/sort o następującym nagłówku:

void qsort(void *base, size_L nmemb, size_l size, int (*r.ompar) (const void *, const void *>)

Tablica do posortowania może być dowolna (typ void), ale musimy dokładnie podać jej rozmiar: ilość elementów nmemb o rozmiarze size. Funkcja ąsort wymaga ponadto jako parametru wskaźnika do funkcji porównawczej. Przy omawianiu list jednokierunkowych dokładnie omówiono pojęcie wskaźników do funkcji, tutaj w celu ilustracji podam tylko gotowy kod do sortowania tablicy liczb całkowitych (przeróbka na sortowanie tablic innego typu niż int wymaga jedynie modyfikacji funkcji porównawczej comp i sposobu wywołania funkcji ąsort):