Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева

Тип: реферат
Категория: Информатика

Скачать

Купить

Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дереваЛабораторная работа № 1Сравнить эффективность методов сортировки массивов:Метод прямого выбора и метод сортировки с помощью дерева.Сортировка с помощью прямого выбора Этот прием основан на следующих принципах: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 6705 12 13 42 44 55 94 6706 12 18 42 44 55 94 6706 12 18 42 44 55 67 94PROCEDURE 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]а[k] := а[i]; a[i] ; = x END END StraightSelectionПрогр. 2.3. Сортировка с помощью прямого выбора,Анализ прямого выбора. Число сравнений ключей (С), очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С имеемс = (n2 - n)/2Число перестановок минимально Mmin=3*(n-l) (2.6)в случае изначально упорядоченных ключей и максимальноMmax = n2/4 +3(n-1)если первоначально ключи располагались в обратном порядке. Для того чтобы определить Mavg, мы должны рассуждать так. Алгоритм просматривает массив, сравнивая каждый элемент с только что обнаруженной минимальной величиной; если он меньше первого, то выполняется некоторое присваивание. Вероятность, что второй элемент окажется меньше первого, равна 1/2, с этой же вероятностью происходят присваивания минимуму. Вероятность, что третий элемент окажется меньше первых двух, равна 1/3, а вероятность для четвертого оказаться наименьшим — 1/4 и т. д. Поэтому полное ожидаемое число пересылок равно Нn—1, где Нn — n-е гармоническое число:Нn=1+1/2+1/3+ ... +1/nНп можно выразить и так: Нп = In n+g+ 1/2n — 1/12n2 + ...где g= 0.577216 ... —константа Эйлера. Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражениемFi-ln i+g+lСреднее число пересылок Mavg в сортировке с выбором есть сумма Fi с i от 1 до n:Mavg=n*(g+l)+(Si: 1Вновь аппроксимируя эту сумму дискретных членов интегралом Integral (1: п) ln x dx == x * (ln x— 1) == n * ln (п)— n + Iполучаем, наконец, приблизительное значение Mavg = n(ln (n) + g)Отсюда можно сделать заключение, что, как правило, алгоритм с прямым выбором предпочтительнее строгого включения. Однако, если ключи в начале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым. 2.3.2. Сортировка с помощью дереваМетод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n —1 элементов и т. д. Обнаружение наименьшего среди п элементов требует—это очевидно — n — 1 сравнения, среди n — 1 уже нужно n — 2 сравнений и т. д. Сумма первых n — 1 целых равна 1/2*(n2 — n). Как же в таком случае можно усовершенствовать упомянутый метод сортировки? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С помощью n/4 сравнений — меньший из пары уже выбранных меньших и т. д. Проделав n — 1 сравнений, мы можем построить дерево выбора вроде представленного на рис. 2,3 и идентифицировать его корень как нужный нам наименьший ключ [2.21.Второй этап сортировки — спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент (дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах (см. рис. 2.4 и 2.5). Элемент, передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После п таких шагов дерево станет пустым (т. е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание — на каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобится порядка n*log n элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего п...

Другие файлы:

Методы внутренней сортировки. Обменная сортировка. Сравнение с другими методами сортировки
Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки вклю...
Алгоритм сортировки массивов
Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки....
Сортировка массивов
Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритм...
Алгоритм быстрой сортировки
Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация...
Исследование алгоритмов топологической сортировки
Анализ структуры топологической сортировки в программной среде. Метод топологической сортировки с помощью обхода в глубину. Программа, реализующая топ...