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 komputera1. Po sporych wahaniach zde cydowałem się jednak nie podejmować problematyki tzw. sortowania zewnętrznego1. 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. 2 Ang. external sorting.
Wyszukiwarka
Podobne podstrony:
img135 10. METODY CIĄGOWE10.1. Uwagi ogólne W tym rozdziale omówimy trzy spośrod wielu znanych metod
ALG3 5.2. Tablicowa implementacja list 123 tego konieczne będzie wybranie jakiejś zmiennej do zapam
79401 img009 (57) 2, METODY DOKŁADNE ROZWIĄZYWANIA UKŁADÓW RÓWNAŃ LINIOWYCH Tematem tego rozdziału s
CV 1 Rozdział 14WYCHOWANIE PREWENCYJNE Problem rodziców polega na tym, że niezależnie od tego, jak w
ALG1 Przedmowa 11 Początkującym zalecane jest trzymanie się porządku narzuconego przez układ rozdzi
ALG9 Rozdział 2Rekurencja Tematem niniejszego rozdziału jest jeden z najważniejszych mechanizmów uż
rozwojówka ćw ( 04 09 i 5 05 091 Rozdział 3 jest ona jeszcze wystarczająco przygotowana, a zatem n
IMG40 (5) Rozdział XIII. Tecntuka pracy materiałami protetycznymi 1« Rozdział XIII. Tecntuka pracy
Hajduk, Pomoc i opieka 1 Rozdział 2 .Wyznaczniki gotowości do pomagania1. Psychologia o gotowości c
1. Moi i molowa Interpretacja przemian cHentfaKiyeft W zadaniach tego rozdziału będziecie się spotyk
P1020276 164 Rozdział V od tego, jak będzie on reagował na konflikt. Wymiar pionowy wskaziye stopień
więcej podobnych podstron