Поиск: 
Расширенный поиск | Последние запросы
FREE-REFERATS.ru

Банк бесплатных рефератов

Бесплатные рефераты > Темы > Компьютеры и программы > Реферат "Метод прямого выбора и метод сортировки с помощью дерева"

Рефераты по Компьютеры и программы - "Метод прямого выбора и метод сортировки с помощью дерева"

Страница: 1 2 3 4
Метод прямого выбора и метод сортировки с помощью дерева
Скачать реферат "Метод прямого выбора и метод сортировки с помощью дерева"
Содержание


Лабораторная работа № 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 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]<xTHEN k:=j; X:= a[k] END BND; а[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 и т. д. Поэтому полное ожидаемое число пересылок равно Нn1, где Н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<i<n; lni)
Вновь аппроксимируя эту сумму дискретных членов интегралом 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*(n

Страница: 1 2 3 4

© 2003-2016 Free-Referat.ru - Рефераты, Курсовые, Дипломы, Доклады, Шпаргалки
Notice: Undefined index: r in /home/bitrix/ext_www/free-referat.ru/index.php on line 264 Notice: Undefined index: in /home/bitrix/ext_www/free-referat.ru/index.php on line 264