Сортировка

Сортировка - это процесс обработки данных, с помощью которого записи в массиве (файле, наборе данных) информации располагаются в установленном порядке согласно принятому критерию. Например, такому критерию, как "по возрастанию (убыванию) значения поля Х в качестве ключа сортировки".

Упорядоченность - это порядок размещения записей относительно друг друга. Обычно упорядоченность осуществляется по наиболее важному полю, называемому ключом сортировки.

Например, телефонный справочник квартирных телефонов:

а) упорядочен по возрастанию фамилий, и.о.;

б) в тоже время относительно адреса - телефонная книга имеет достаточно случайный характер.

Ключ сортировки может быть составным, т.е. состоять из нескольких полей. Причем, каждое поле может иметь свой порядок.

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

Существуют программы сортировки для выполнения этой процедуры обработки данных. Такие программы могут входить в состав ОС, систем программирования, комплексов утилит (сервисных программ) и т.д.

Файл (исходный) -> сортировка -> Файл (результирующий)

Для оценки методов упорядочения одним из основных критериев является количество операций сравнения в процессе сортировки.

Теоретически доказано, что минимально возможное число сравнений для упорядочения nэлементов (записей) приближенно оценивается по формуле:

C(n)

С - число операций сравнения;

n - количество записей в массиве;

]x[ - наименьшее целое, не меньшее х.

Сортировка - процесс расположения записей согласно принятому критерию.

Сортировки подразделяют в зависимости от алгоритма и вида используемой при сортировке памяти на:

- внутренние (пузырьковая, Шелла, вставки, квадратичной выборки) в оперативной памяти;

- внешние (балансная, каскадная, многофазная) с использования внешних носителей информации.

Методы сортировки:

Метод пузырька.

Очень простой, но не эффективный способ. Название получил по аналогии с пузырьком, всплывающим в жидкости. Сортировка проводится по алгоритму: первый ключ сравнивается со всеми последующими, пока не будет найден ключ j-й ключ, меньший первого. Тогда ключи меняются местами, т.е. делается их перестановка. Таким образом, совершается процедура со всеми последующими ключами до конца массива. Для первого ключа требуется (n-1) сравнение. Затем берется второй ключ и процедура повторяется, осуществляется (n-2) сравнения. И т.д. до (n-1)-го ключа, который сравнивается с последним, одно сравнение.

Всего проводится сравнений:

C(n)=(n-1)+(n-2)+...+1=n(n-1)/2.

Число возможных перестановок ключей: max P(n)»n(n-1)/2, среднее P(n)»n(n-1)/4.

Метод вставки.

При этом методе сортировки каждый ключ (обозначим его номером j) сравнивается с предыдущим до тех пор, пока не будет найден ключ с меньшим значением, чем ключ с номером j. Пусть это будет ключ с номером k (k<j). Тогда все ключи с номерами k+1,....j-1 сдвигаются на одну позицию вниз, а ключ j ставится на место ключа к+1. Если все впереди стоящие ключи больше ключа j, то все предыдущие сдвигаются вниз и ключ j ставится первым. Таким образом, доходят до последнего ключа n.

Оценка числа сравнений C(n)»n(n-1)/4.

Число перестановок ключей в процессе сортировки оценивается как P(n)»n(n-1)/4.

Метод Шелла.

Этот метод заключается в разбивке массива на группы и сортировке внутри этих групп. Затем группы попарно сливаются и производится сортировка внутри вновь образованных групп и т.д. На последнем этапе, когда массив представляет две отсортированные группы, он сортируется методом вставки или с помощью слияния с одновременным итоговым упорядочением.

Первоначально группы состоят из двух элементов, например, из 1-го и [n/2]+1-го, 2-го и [n/2]+2-го и т.д.

При использовании метода Шелла время сортировки пропорционально, как подтверждено экспериментально, .

Число сравнений С(n) £ 0.5n.

Внешние сортировки (на внешнем носителе):

Для больших объемов информации используются, как правило, внешние запоминающие устройства (ВЗУ) - магнитные ленты, диски. Сортировки с применением ВЗУ называются внешними. Внешние сортировки проводятся обычно в два этапа. На первом этапе выполняется внутренняя сортировка отдельных блоков информации и эти блоки записываются на внешние носители. На втором этапе эти блоки сливаются в один массив. Под слиянием будем понимать формирование из нескольких блоков такой части массива, которая упорядочена по тем же правилам, что и исходные блоки.

Существует несколько видов внешних сортировок.

Балансная сортировка.

Известны модификации этой сортировки - метод слияния, обменная сортировка.

При сортировке этим методом рабочий объем оперативной памяти делится на р-вводных и одну выводную зону. Обычно р=2. Для сортировки требуется 2р магнитных лент или файлов на магнитном диске. Исходный массив записывается на р лентах упорядоченными блоками равной длины. Другие р-лент считаются выходными. С каждой ленты считывается блок (всего р-блоков) в одну зону, информация в которой сортируется и выводится на очередную выходную ленту. Упорядоченная порция будет в р-раз больше, чем были входные порции. Это выполняется до тех пор, пока выходной порцией не окажется весь массив.

Рассмотрим пример. Пусть р=2. Массив состоит из 10 записей. Схема сортировки будет выглядеть следующим образом.

Исходный 1-й этап 2-й этап 3-й этап Выходной

массив массив

Дата добавления: 2013-12-14