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


Краткая теория


 

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

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

§       внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины

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

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

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

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

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

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

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

 

Рассмотрим второй критерий подробнее: мы можем подсчитать количество сравнений при выполнении сортировки или количество перемещений.

         Предположим, что число сравнений определяется формулой:

C = 0,01n2 + 10n

Если n<1000, то второе слагаемое больше.

Если n>1000, то первое слагаемое больше.

То есть, при малых n порядок сравнения равен , а при больших n он равен n.

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

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

§       улучшенные методы

 

Рассмотрим преимущества прямых методов:

1.


- Начало -  - Назад -  - Вперед -



Книжный магазин