algorytmy. wydanie iv helion.pdf

SPIS TRE CI

Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1 Podstawy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.1

Podstawowy model programowania

1.2

Abstrakcja danych

1.3

Wielozbiory, kolejki i stosy

132

1.4

Analizy algorytmów

184

1.5

Studium przypadku — problem Union-Find

228

2 Sortowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

2.1

Podstawowe metody sortowania

256

2.2

Sortowanie przez scalanie

282

2.3

Sortowanie szybkie

300

2.4

Kolejki priorytetowe

320

2.5

Zastosowania

348

3 Wyszukiwanie . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

3.1

Tablice symboli

374

3.2

Drzewa wyszukiwa binarnych

408

3.3

Zbalansowane drzewa wyszukiwa

436

3.4

Tablice z haszowaniem

470

3.5

Zastosowania

498

Poleć książkę

Kup książkę

4 Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

4.1

Grafy nieskierowane

530

4.2

Grafy skierowane

578

4.3

Minimalne drzewa rozpinajce

616

4.4

Najkrótsze cieki

650

5 Łacuchy znaków . . . . . . . . . . . . . . . . . . . . . . . . . 706

5.1

Sortowanie łacuchów znaków

714

5.2

Drzewa trie

742

5.3

Wyszukiwanie podłacuchów

770

5.4

Wyraenia regularne

800

5.5

Kompresja danych

822

6 Kontekst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

Algorytmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944

Klienty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945

Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946

Poleć książkę

Kup książkę

S ortowanie to proces porz dkowania obiektów w logiczny sposób. Przykładowo,

na wydruku dla u ytkownika karty kredytowej transakcje s uporz dkowane

chronologicznie. Kolejno ta została prawdopodobnie wyznaczona przez algo-

rytm sortowania. W pocz tkowym okresie rozwoju informatyki szacowano, e do 30%

wszystkich cykli procesora po wi canych jest na sortowanie. To, e obecnie odsetek

ten jest ni szy, wynika z tego, i algorytmy sortowania s stosunkowo wydajne, a nie ze

zmniejszenia znaczenia tej operacji. Wszechobecno komputerów sprawia, e dost p-

nych jest mnóstwo danych, a pierwszym krokiem przy ich organizowaniu jest cz sto

sortowanie. We wszystkich systemach komputerowych istniej implementacje algoryt-

mów sortowania dost pne dla systemu i u ytkowników.

S trzy praktyczne powody, dla których warto pozna algorytmy sortowania

(mimo e mo na zastosowa sortowanie systemowe).

Analiza algorytmów sortowania jest solidnym wprowadzeniem do podej cia

u ywanego przy porównywaniu wydajno ci algorytmów w tej ksi ce.

Podobne techniki s skuteczne w rozwi zywaniu innych problemów.

Algorytmy sortowania cz sto słu za punkt wyj cia przy rozwi zywaniu in-

nych problemów.

Wa niejsze od tych praktycznych powodów jest to, e algorytmy sortowania s ele-

ganckie, klasyczne i skuteczne.

Sortowanie odgrywa kluczow rol w komercyjnym przetwarzaniu danych

i współczesnych obliczeniach naukowych. Istnieje wiele zastosowa takich algoryt-

mów w obszarze przetwarzania transakcji, optymalizacji kombinatorycznej, astro-

zyki, dynamiki molekularnej, lingwistyki, bada nad genomem, prognozowania

pogody itd. Jeden z algorytmów sortowania (sortowanie szybkie, opisane w -

. ) został uznany za jeden z 10 najwa niejszych algorytmów XX wieku

w dziedzinie nauki i in ynierii.

W tym rozdziale omówiono kilka klasycznych metod sortowania i wydajn imple-

mentacj wa nego typu danych — kolejki priorytetowej. Opisano teoretyczne pod-

stawy porównywania algorytmów sortowania, a rozdział zako czono analiz zasto-

sowa sortowania i kolejek priorytetowych.



255

Poleć książkę

Kup książkę

2.1. PODSTAWOWE METODY SORTOWANIA

do krainy algorytmów sortowania analizujemy

dwie podstawowe metody sortowania i odmian jednej z nich. Oto niektóre powody

do zapoznania si z tymi stosunkowo prostymi algorytmami. Po pierwsze, zapewnia-

j one kontekst, w którym mona pozna terminologi i podstawowe mechanizmy.

Po drugie, te proste algorytmy s w niektórych zastosowaniach wydajniejsze od za-

awansowanych algorytmów omówionych dalej. Po trzecie, jak si okae, pozwalaj

poprawi wydajno bardziej skomplikowanych rozwiza.

Reguły Zajmujemy si przede wszystkim algorytmami do zmiany kolejno ci

w tablicach elementów , w których ka dy element posiada klucz . Zadaniem algorytmu

sortowania jest zmiana kolejno ci elementów, tak aby klucze były uporz dkowane

według dobrze zde niowanej reguły (zwykle w porz dku liczbowym lub alfabetycz-

nym). Nale y uporz dkowa tablic , eby klucz ka dego elementu był nie mniejszy

ni klucz na ka dej pozycji o ni szym indeksie i nie wi kszy ni klucz w elementach

o wi kszych indeksach. Specy czne cechy kluczy i elementów mog by bardzo ró -

ne w poszczególnych zastosowaniach. W Javie elementy s obiektami, a abstrakcyjne

poj cie „klucz” jest uj te we wbudowanym mechanizmie — opisanym na stronie 259

interfejsie Comparable .

Klasa Example , przedstawiona na nast pnej stronie, to ilustracja zastosowanych

konwencji. Kod sortuj cy umieszczono w metodzie sort() w tej samej klasie, co

prywatne funkcje pomocnicze less() i exch() (a czasem tak e kilka innych) oraz

przykładowego klienta main() . W klasie Example znajduje si te kod, który mo e by

przydatny przy wst pnym diagnozowaniu. Klient testowy main() sortuje ła cuchy

znaków ze standardowego wej cia i u ywa prywatnej metody show() do wy wiet-

lenia zawarto ci tablicy. W dalszej cz ci rozdziału zbadano ró ne klienty testowe,

słu ce do porównywania algorytmów i analizowania ich wydajno ci. Aby rozró ni

metody sortowania, ró nym klasom nadano inne nazwy. W klientach mo na wy-

woływa ró ne implementacje za pomoc specy cznych nazw: Insertion.sort() ,

Merge.sort() , Quick.sort() itd.

Kod sortuj cy przewa nie korzysta z danych za pomoc tylko dwóch operacji:

metody less() , która porównuje elementy, oraz metody exch() , zamieniaj cej je

miejscami. Implementowanie metody exch() jest łatwe, a interfejs Comparable uła-

twia implementowanie metody less() . Poniewa dost p do danych maj tylko te

dwie operacje, kod jest czytelny i przeno ny, a ponadto łatwo jest sprawdza popraw-

no algorytmów, bada ich wydajno ci oraz porównywa je. Przed przej ciem do

implementacji sortowania omówiono liczne wa ne kwestie, które trzeba starannie

przemy le dla ka dej techniki sortowania.

256

Poleć książkę

Kup książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: