Структуры и алгоритмы обработки данных

       

Сортировка


При обработке данных важно знать  информационное поле данных и размещение их в машине.

Различают внутреннюю и внешнюю сортировку:

- внутренняя сортировка - сортировка в оперативной памяти;

- внешняя сортировка - сортировка во внешней памяти.

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

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

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

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

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

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

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

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

Порядок числа сравнения при сортировке лежит в пределах от  О (n log n)   до О (n2);    О (n) - идеальный  и недостижимый случай.

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

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

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

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

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

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

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

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



Содержание раздела