............................................................... 175
CallCountingListComparator .................................................................................. 176
ListSorterCallCountingTest .................................................................................... 177
Jak interpretować wyniki tej analizy? ....................................................................... 180
Podsumowanie .......................................................................................................... 180
Ćwiczenia .................................................................................................................. 181
Spis
treści 5
Rozdział 7. Sortowanie zaawansowane .................................................................................................183
Sortowanie metodą Shella .......................................................................................... 183
Sortowanie szybkie .................................................................................................... 189
Komparator złożony i jego rola w zachowaniu stabilności sortowania .............................. 195
Sortowanie przez łączenie ........................................................................................... 198
Łączenie list ......................................................................................................... 198
Algorytm Mergesort ............................................................................................... 199
Porównanie zaawansowanych algorytmów sortowania ................................................... 205
Podsumowanie .......................................................................................................... 208
Ćwiczenia .................................................................................................................. 209
Rozdział 8. Kolejki priorytetowe .............................................................................................................211
Kolejki priorytetowe .................................................................................................... 212
Prosty przykład kolejki priorytetowej ....................................................................... 212
Wykorzystywanie kolejek priorytetowych ....................................................................... 215
Kolejka priorytetowa oparta na liście nieposortowanej ............................................. 218
Kolejka priorytetowa wykorzystująca listę posortowaną ............................................ 220
Kolejki priorytetowe o organizacji stogowej .............................................................. 222
Porównanie implementacji kolejek priorytetowych ......................................................... 229
Podsumowanie .......................................................................................................... 233
Ćwiczenia .................................................................................................................. 233
Rozdział 9. Binarne wyszukiwanie i wstawianie .................................................................................235
Wyszukiwanie binarne ................................................................................................ 235
Dwa sposoby realizacji wyszukiwania binarnego ...................................................... 238
Interfejs wyszukiwania binarnego ........................................................................... 238
Iteracyjna wyszukiwarka binarna ............................................................................. 244
Ocena działania wyszukiwarek ............................................................................... 247
Wstawianie binarne .................................................................................................... 253
Inserter binarny .................................................................................................... 254
Porównywanie wydajności ...................................................................................... 257
Podsumowanie .......................................................................................................... 261
Rozdział 10. Binarne drzewa wyszukiwawcze ....................................................................................263
Binarne drzewa wyszukiwawcze ................................................................................... 264
Minimum ............................................................................................................. 265
Maksimum ........................................................................................................... 265
Następnik ............................................................................................................ 265
Poprzednik ........................................................................................................... 266