Элементарные методы сортировки

В качестве нашей первой экскурсии в область алгоритмов сортировки, мы изучим некоторые «элементарные» методы которые хорошо работают для небольших файлов или файлов специальной структуры. Существует несколько причин, по которым желательно изучение этих простых методов. Во-первых, они дают нам относительно безболезненный способ изучить терминологию и основные механизмы работы алгоритмов сортировки, что позволяет получить необходимую базу для изучения более сложных алгоритмов. Во-вторых, для многих задач сортировки бывает лучше использовать простые методы, чем более сложные алгоритмы. И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных.

В некоторых программах сортировки лучше использовать простые алгоритмы. Программы сортировки часто используются только один раз (или несколько раз). Если количество элементов, которые нужно отсортировать не велико (скажем меньше чем 500 элементов), то может статься, что использование простого алгоритма будет более эффективно, чем разработка и отладка сложного алгоритма. Элементарные методы всегда пригодны для маленьких файлов (скажем меньших, чем 50 элементов); маловероятно, что сложный алгоритм было бы разумно использовать для таких файлов, если конечно не нужно сортировать большое количество таких файлов.

Как правило, элементарные методы, которые мы будем обсуждать, производят около операций для сортировки N произвольно взятых элементов. Если N достаточно мало, то это может и не быть проблемой, и если элементы распределены не произвольным образом, то эти алгоритмы могут работать даже быстрее, чем сложные. Однако следует запомнить то, что эти алгоритмы не следует использовать для больших, произвольно упорядоченных файлов, с одним единственным исключением для алгоритма оболочечной сортировки, который часто используется во многих программах.

Правила Игры

Перед тем, как рассматривать какой-либо конкретный алгоритм, было бы полезно изучить терминологию и некоторые основные соглашения об алгоритмах сортировки. Мы будем изучать алгоритмы для сортировки файлов записей содержащих ключи. Ключи, которые являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в некотором строго определенном порядке (обычно в алфавитном или числовом).

Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой. Главное отличие между ними состоит в том, что при внутренней сортировке любая запись легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками. Большинство алгоритмов сортировки, которые мы рассмотрим – внутренние.

Обычно, главное, что будет нас интересовать в алгоритме – это время его работы. Первые четыре алгоритма, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное , в то время как более сложные алгоритмы используют время пропорциональное . ............