ALG1

Rozdział 4

Algorytmy sortowania

Tematem tego rozdziału będzie opis kilku bardziej znanych metod sortowania danych. O użyteczności tych zagadnień nie trzeba chyba przekonywać; każdy programista prędzej czy później z tym zagadnieniem musi mieć do czynienia. Opisy metod sortowania będą dotyczyły wyłącznie tzw. sortowania wewnętrznego, używającego wyłącznie pamięci głównej komputera¹. Po sporych wahaniach zde cydowałem się jednak nie podejmować problematyki tzw. sortowania zewnętrznego¹. Sortowanie zewnętrzne dotyczy sytuacji, z którą większość Czytelników być może nigdy się nie zetknie w praktyce programowania: ilość danych do sortowania jest tak olbrzymia, że niemożliwa do umieszczenia w pamięci w celu posortowania ich przy pomocy jednej z wielu metod sortowania „wewnętrznego”.

Dlaczego przyjmuję tak optymistyczną hipotezę? W chwili obecnej jest zauważalne systematyczne tanienie nośników pamięci RAM i dysków twardych. Proces ten jest nieodwracalny i jedyne, o co się można spierać, to stopień jego zaawansowania.

Mój pierwszy prywatny komputer osobisty typu IBM PC XT miał 1MB RAM i dysk twardy 20MB. Od tego momentu minęło zaledwie kilka lat: dzisiaj większość programów nie chciałaby zwyczajnie wystartować z tak małą ilością pamięci, a objętość 20MB jest wystarczająca na instalację pojedynczego programu... Coraz głośniej zaczyna być o bazach danych całkowicie rezydujących w pamięci (dla zwiększenia sprawności), rzecz niewyobrażalna kilka lat temu w praktyce. W konsekwencji takiego status quo zdecydowałem się nie poświęcać sortowaniu zewnętrznemu specjalnej uwagi. Osoby zainteresowane odnajdą szczegółowe informacje na przykład w [AHU87], [FGS90], [Knu75], [Sed92] - mam nadzieję, że większość Czytelników odniesie się do tego posunięcia ze zrozumieniem.

' Ang. internal sorting. ² Ang. external sorting.