:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Сортировка » FAQ
  FAQ версия 2.21



Для удобства редактирования весь FAQ представлен в виде чистого текста, с минимумом ссылок, и без изображений.

В процессе работы над FAQом я смотрел многие источники по этим вопросам, в которых(даже написанных самыми уважаемыми авторами) зачастую давались разные, иногда противоречивые сведения. Особенно это касается характеристик сортировок.

В FAQ были включены те, которые я счел правильными. Однако 'субъективных' оценок алгоритмов не бывает, поэтому по всем вопросам, вызывающим аргументированные сомнения, пишите мне на адрес:

Kantor Ilia
e-mail: algolist@manual.ru
web: http://algolist.manual.ru


  Вопросы



1. Ликбез для понимания важной информации:
     Что означает символ O(n) ? Оценки Omega() и Theta()
     Почему _не пишется_ основание логарифма: O(logn) ?

2. Какие на сегодняшний день самые эффективные методы сортировки ?

3. Описание и исходник SelectSort (сортировка выбором).

4. Сортировка пузырьком BubbleSort и ее улучшения с исходниками.

5. Описание и исходник InsertSort (сортировка простыми вставками).

6. Описание и исходник ShellSort (сортировка Шелла).

7. Описание и исходник сортировки двоичным деревом
     (TreeSort, 'древесная сортировка'). Выбор с замещением.

8. Описание и исходник QuickSort (быстрая сортировка).

9. Описание и исходник HeapSort (пирамидальная сортировка).

10. Описание MergeSort (сортировка слиянием).

11. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?

12. Требования и свойства сортировок. Что когда лучше?
     12.1 Какая самая быстрая сортировка ?
     12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?

13. Есть большой файл. Как его отсортировать ? Многофазное слияние.

App. Использованная литература.