Сравнить эффективность методов сортировки массивов:
Метод прямого выбора и метод сортировки с помощью дерева.
Сортировка с помощью прямого выбораЭтот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом ai.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1, приведен в табл. 2.2. Алгоритм формулируется так:
FORi:=ITO n-1 DO
присвоить k индекс наименьшего из a[i],,, a[nJ; поменять местами a[i] и a[j];
end
Такой метод – его называют прямым выбором – в некотором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность. Полностью алгоритм прямого выбора приводится в прогр. 2.3.
Таблица 2.2. Пример сортировки с помощью прямого выбора
Начальные ключи
44 55 12 42 94 18 06 67
06 55 12 42 94 18 44 67
06 12 55 42 94 18 44 67
06 12 18 42 94 55 44 67
05 12 18 42 94 55 44 67
05 12 13 42 44 55 94 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
PROCEDURE StraightSfcleclion;
VAR i,j,k: index; x: item; BEGIN
FORi:=1 TO n-1 DO k:= i; x := a[i]; FORj:= i+1TO n DO
IF a[j]
Похожие работы
... данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве. Наконец, сортировка ...
... же операции в сортировке с помощью N-путевого слияния, разница только в том, что здесь алгоритм исключения последовательности несколько проще. Глава 2. Практические задачи по алгоритмам обработки данных 2.1 Решение задачи о пяти ферзях Постановка задачи: Найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находится под ударом хотя одного из них. Задача о пяти ...
... не повторяются. Простой путь – путь, в котором дуги не повторяются. Маршрут – последовательность ребер, составляющих, как и путь, цепочку. Длина пути взвешенного графа определяется как сумма весов – его дуг. Если граф не взвешен, то можно считать веса дуг равными 1. Кратчайшим путем между выделенной парой вершин хн и хк называется путь, имеющий наименьшую длину среди всех возможных путей между ...
... 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути. 3) (Y mod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер. 2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР 2.1 Математическое описание задачи Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию. Сортировка используется для ...
0 комментариев