Читайте также:
|
Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, і, Ј. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. Рассмотрим различные алгоритмы сортировки и выясним, почему возникла необходимость появления такого большого числа алгоритмов решения одной и той же задачи.
Вообще, алгоритмы сортировки - одна из самых хорошо исследованных областей информатики. Тем не менее не исключены открытия и в этой области, потому что наверняка существуют еще какие-то пока неизвестные методы сортировки, основанные на новых принципах и идеях.
Традиционно различают внутреннюю сортировку, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы (для методов, основанных на сравнении, число сравнений, обменов элементов и пр.), и внешнюю, в которой данные хранятся на внешнем устройстве с медленным доступом (магнитные лента, барабан, диск) и прежде всего надо снизить число обращений к этому устройству.
Стоит заметить, что алгоритм сортировки слиянием удобно применять и при сортировке внешних данных. При этом речь будет идти о слиянии файлов.
Сложность алгоритма - одночлен, отражающий порядок величины требуемого ресурса (времени/дополнительной памяти) в зависимости от размерности задачи.
· Сортировка подсчетом - суть метода заключается в том, что на каждом шаге мы подсчитываем, в какую позицию результирующего массива надо записать очередной элемент исходного массива.
· Сортировка включением - в этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.
· Простое включение - пусть отсортировано начало массива A[1], A[2],..., A[i-1], а остаток массива A[i],...,A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый - с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.
· Метод Шелла - метод Шелла является усовершенствованием простого включения, которое основано на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле мы избавлялись от сдвига A[i], сохраняя его в промежуточной переменной, но сути метода это не изменяло, так как передвигалось место, оставленное под сохраненное значение).
· Сортировка извлечением - в этих методах массив также делится на уже отсортированную часть A[i+1], A[i+1],..., A[n] и еще не отсортированную A[1], A[2],..., A[i]. Но здесь из неотсортированной части на каждом шаге мы извлекаем максимальный элемент. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы мы извлечем на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части.
· Простое извлечение - при простом извлечении мы будем искать максимальный элемент неотсортированной части, просматривая ее заново на каждом шаге. Найдя положение максимального элемента поменяем его с A[i] местами.
· Древесная сортировка - древесная сортировка избегает необходимости каждый раз находить максимальный элемент. При следовании этому методу постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом.
· Сортировка обменами - сортирует массив путем последовательных обменов пар элементов местами.
· Пузырьковая сортировка - один из наиболее широко известных алгоритмов сортировки. В этом методе массив также делится на две части: отсортированную и неотсортированную. На каждом шаге метода мы пробегаем от меньших индексов к большим по неотсортированной части, каждый раз сравнивая два соседних элемента: если они не упорядочены между собой (меньший следует за большим), то меняем их местами. Тем самым за один проход путем последовательных обменов наибольший элемент неотсортированной части сдвинется к ее концу.
· Быстрая сортировка (Хоара) - на каждом шаге метода мы сначала выбираем «средний» элемент, затем переставляем элементы массива так, что он делится на три части: сначала следуют элементы, меньшие «среднего», потом равные ему, а в третьей части - большие. После такого деления массива остается только отсортировать первую и третью его части, с которыми мы поступим аналогично (разделим на три части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован.
· Сортировка слиянием - этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием.
Пусть k - положительное целое число. Разобьем массив A[1]..A[n] на отрезки длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.) Последний отрезок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.
· Сортировка распределением - сортирует массив, не сравнивая элементы друг с другом.
· Вырожденное распределение - …..
· Сортировка распределением - пусть мы можем завести дополнительную память размером M+N, а элементы массива могут принимать значения от 0 до S, причем S>>M.
Каждый элемент этого массива можно представить в M-ичной системе счисления и разбить на K цифр этой системы счисления.
Заведем M списков общей суммарной длиной порядка N (это можно сделать, ограничившись дополнительной памятью O(M+N)).
Дата добавления: 2015-02-16; просмотров: 94 | Поможем написать вашу работу | Нарушение авторских прав |