Понятие сортировки, ее эффективность; классификация методов сортировки

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

Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, то есть делают перестановку указателей, а сам массив не перемещается. Это - метод сортировки таблицы адресов.

При сортировке могут встретиться одинаковые ключи. В этом случае желательно после сортировки расположить одинаковые ключи в том же порядке, что и в исходном файле.
Это - устойчивая сортировка.

Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются «на том же месте».

Эффективность сортировки можно рассматривать по нескольким критериям:

• время, затрачиваемое на сортировку;

• объем оперативной памяти, требуемой для сортировки;

• время, затраченное программистом на написание программы.

Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений и количество перемещений при выполнении сортировки.

• Порядок числа сравнений и перемещений при сортировке лежит в пределах

от О (n log n) до О (n 2);

О (n) - идеальный и недостижимый случай.

Различают следующие методы сортировки:

• строгие (прямые) методы;

• улучшенные методы.

Строгие методы:

• метод прямого включения;

• метод прямого выбора;

• метод прямого обмена.

Эффективность строгих методов примерно одинакова.