Сортування й пошук: Рецептурний довідник

ЗМІСТ

1.     Введение                                                                                                                       4

2.     Сортировка                                                                                                                  8

2.1     Сортування вставками                                                                                                                            8

2.2     Сортування Шелла                                                                                                                                   9

1.3     Швидке сортування                                                                                                                                11

1.4     Порівняння методів                                                                                                                                14

3.     СЛОВНИКИ                                                                                                                     15

3.1     Хеш-таблицы                                                                                                                                            15

1.2     Пошук у бінарних деревах                                                                                                                   19

1.3     Червоно-чорні дерева                                                                                                                            22

1.4     Розділені списки                                                                                                                                      27

3.5     Порівняння методів                                                                                                                                29

4.     ТЕКСТИ ПРОГРАМ                                                                                                        32

4.1     Коди для сортування вставками                                                                                                        32

4.2     Коди для сортування Шелла                                                                                                               33

4.3     Коди для швидкого пошуку (функції Quicksort)                                                                          34

4.4     Коди для стандартної реалізації швидкого пошуку                                                                    36

4.5     Коди для хеш-таблиц                                                                                                                             37

4.6     Коди для бінарних дерев                                                                                                                       39

4.7     Коди для червоно-чорних дерев                                                                                                         41

4.8     Коди для розділених списків                                                                                                               47

5.     ЛІТЕРАТУРА                                                                                                                  50

6.     СЛОВНИК                                                                                                                       51

Передмова

У цій книжечці втримується інформація про декілька алгоритмів сортування й пошуку. Цю інформацію можна знайти в безлічі книг - у більшості з них передбачається знання математичного аналізу й теорії ймовірностей. Хоча формальне дослідження алгоритмів і доказ результатів, що описують їх асимптотические властивості, дуже важливі, часто важливі й можливі чисто інтуїтивні пояснення.

      Тут всі алгоритми пояснені в найбільш простому виді. Передбачається, що ви володієте Си або Паскалем принаймні на початковому рівні. Зокрема, ви повинні знати, що таке масиви й покажчики. Матеріал представлений тут у порядку від простого до ледве більше складного. Незважаючи на те, що цей текст призначений для початківців, у ньому є розділи, які можуть виявитися цікавими й більше просунутим читачам. Особливо це ставиться до розділів про хеш-таблицах і скіпи-списки.

Санта-Круз, Каліфорнія                                                                                       Томас Ниман

Березень 1995

Зауваження перекладача

При читанні RU.ALGORITHMS у російському ФИДО я часто натикаюся на малограмотні й/або невірні твердження. Цей текст здався мені цікавим для початківців - він, принаймні, убереже їх від зовсім уже непрощенних оман.

Москва                                                                                                                  Павло Дубнер