Ключи хранятся либо вместе с элементами, либо вместе с указателями.
Основной характеристикой алгоритма сортировки является показатель вычислительной сложности, зависящий от количества сортируемых элементов n. Элементарные методы сортировки требуют О(n2) шагов. Более совершенные методы имеют показатель О(nlogn).
Аналитические оценки получены на основе подсчета базовых операций сравнения и обмена. Как правило, эти операции сосредоточены во внутренних циклах алгоритма. Поэтому эти циклы максимально упрощены за счет удаления по возможности вспомогательных команд.
Вторым показателем эффективности алгоритма сортировки является объем дополнительной памяти, используемый для сортировки. По этому показателю алгоритмы делятся на три группы:
1. алгоритмы, которые организуют сортировку на том же месте и не используют дополнительную память, за исключением стека или таблицы.
2. алгоритмы, которые используют представление в виде связанного списка или другие структуры указателей или индексов.
3. алгоритмы, которые требуют дополнительную память для размещения еще одной копии массива для сортировки.
Элементарные методы сортировки.
Сортировка выбором.
Сначала ищется минимальный элемент в массиве A[1…n] и меняется местами с первым элементом в массиве. Далее находится второй минимальный элемент в массиве A[2…n] и меняется местами со вторым элементом и т.д. Т.е. алгоритм работает по принципу выбора наименьшего элемента из числа несортированных.
 |
44 55 12 42 94 06
06 55 12 42 94 44
 |
06 12 55 42 94 44
06 12 42 55 94 44
06 12 42 44 94 55
06 12 42 44 55 94
Selection_Sort (A)
1.
for i
1 to length(A)-1
2.
do iminI
3.
for jI+1 to
length(A)
4. do if A[j]<A[imin]
5.
then iminj
6.
tempA[imin]
7.
A[imin] A[i]
8.
A[i] temp
Основную составляющую времени представляет количество операций сравнения во внутреннем цикле (строка 4). Это время пропорционально n2 . Количество операций обмена равно n-1.
Недостатком сортировки выбором является то, что время выполнения алгоритма мало зависит от упорядоченности массива. На сортировку почти отсортированного файла или файла, где много одинаковых ключей, уходит столько же времени, что и на сортировку файла, упорядоченного случайным образом.
Однако этому методу надо отдать предпочтение, когда элементы файла имеют большой размер, а ключи занимают небольшой объем. В этом случае затраты на перемещение больших элементов минимальны при небольшой стоимости операций сравнения.
Сортировка вставками.
При сортировке вставками каждый очередной элемент помещается в надлежащее место среди отсортированных элементов. Для освобождения места для вставляемого элемента производится смещение части элементов в отсортированной части на одну позицию вправо.
44 55 12 42 94 06
 |
44 55 12 42 94 06
 |
12 44 55 42 94 06
12 42 44 55 94 06
12 42 44 55 94 06
 |
06 12 42 44 55 94
Insertion_Sort (A)
1. for j2 to length[A]
2.
do keyA[j]
3.
добавить A[j] к отсортированной части A[1…j-1]
4.
ij-1
5. while i>0 and A[j]>key
6.
do A[i+1]A[i]
7. ii-1
8. A[i+1] key
Алгоритм можно улучшить, убрав проверку i>0 в цикле while. Для этого перед сортировкой в массиве ищется минимальный элемент и помещается в первую позицию массива. После этого можно приступить к сортировке, не проверяя начало массива во внешнем цикле.
В отличие от сортировки выбором сортировка вставками зависит от исходного порядка ключей в файле. Если ключи уже упорядочены, то сортировка вставками протекает быстро.
Обменная сортировка (пузырьковая).
Алгоритм выполняет повторные проходы по файлу с обменом местами соседних элементов, нарушающих заданный порядок. Проходы прекращаются, когда файл окажется отсортированным. Пузырьковый метод в общем случае обладает меньшим быстродействием.
Bubble_Sort (A)
1.
for i1 to length[A]-1
2.
do for jlength[A]
down i-1
3. do if A[j-1]<A[j]
4.
then tempA[j]
5.
A[j] A[j-1]
6.
A[j-1] temp
Достаточно выполнить n проходов. За каждый проход очередной минимальный элемент перемещается на первую позицию в неотсортированной части.
44 55 12 42 94 06
06 44 55 12 42 94
06 12 44 55 42 94
06 12 42 44 55 94
06 12 42 44 55 94
Представленный алгоритм не является адаптивным. Его можно улучшить, проверяя, не оказался ли очередной проход таким, что на нем не было выполнено ни одной операции перестановки. Если файл полностью упорядочен, то не произойдет ни одной перестановки и внешний цикл можно прекратить. Однако внедрение подобного усовершенствования не достигает эффективности алгоритма сортировки вставками, в которм осуществляется прерывание внутреннего цикла, а не внешнего.
Все представленные алгоритмы сортировки характеризуются оценкой эффективности О(n2), но не нуждаются в дополнительной памяти. Время выполнения этих алгоритмов отличается только коэффициентом пропорциональности.
Сортировка выбором производит примерно n2/2 сравнений и n операций обмена. Сортировка всатвками производит приблизительно n2/4 сравнений
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.