Основные методы внутренней сортировки

Классификация методов сортировки

Существует несколько признаков, по которым можно различать методы сортировки (прил.).

1. По месту проведения работы различают сортировку массивов записей, целиком расположенных в основной памяти - внутреннюю сортировку, и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти - внешнюю сортировку. Для внутренней и внешней сортировки требуются разные методы, так как:

1) внутренние сортировки работают с данными в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат;

2) внешние сортировки упорядочивают информацию, расположенную на внешних носителях. Это накладывает некоторые дополнительные ограничения на алгоритм:

· объем данных не позволяет им разместиться в ОЗУ;

· доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью;

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

Внешняя сортировка оперирует с запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (сортировка файлов), т.е. в данный момент доступен только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство.

2. По способу выполнения работы алгоритмы сортировки различают по следующим позициям:

· сортировка вставками - элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов;

· обменные сортировки – если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены;

· сортировка посредством выбора – сначала выделяется наименьший или наибольший элемент и каким-либо образом отделяется от остальных. Затем выбирается наименьший или наибольший элемент из оставшихся;

· сортировка подсчетом – каждый элемент сравнивается со всеми остальными. Окончательное положение элемента определяется подсчетом числа меньших ключей.

Естественным условием, предъявляемым к любому методу внутренней сортировки, является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).

С этой точки зрения различают квадратичные и субквадратичные алгоритмы и логарифмические и линейные алгоритмы.

Примером квадратичных и субквадратичных алгоритмов являются:

· сортировка выбором(SelectSort);

· сортировка пузырьком(BubbleSort) и ее улучшения;

· сортировка простыми вставками(InsertSort)4

· сортировка Шелла (ShellSort).

Примером логарифмических и линейных алгоритмов являются:

· пирамидальная сортировка (HeapSort);

· быстрая сортировка (QuickSort);

· поразрядная сортировка(RadixSort).

Дата добавления: 2014-12-27