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


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


 

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

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

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

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

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

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

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

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

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

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

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

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

Пусть Н = 0,01n2 + 10n - число сравнений. Если n < 1000, то второе слагаемое больше, если n > 1000, то больше первое слагаемое.

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

Порядок сравнения при сортировке лежит в пределах

от 0 (n log n)  до 0 (n2); 0 (n) - идеальный случай.

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

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

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

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

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

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

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

Количество перемещений в этих трех методах примерно одинаково.

 

 

   3.2.1 Сортировка методом прямого включения




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