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

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

Лабораторная работа № 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]а[k] := а[i]; a[i] ; = x END END StraightSelection

Прогр. 2.3. Сортировка с помощью прямого выбора,

Анализ прямого выбора. Число сравнений ключей (С), очевидно, не зависит от начального порядка клю­чей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение пря­мого включения. Для С имеем

с = (n² - n)/2

Число перестановок минимально Mmin=3*(n-l) (2.6)

в случае изначально упорядоченных ключей и макси­мально

M_max = n² /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/12n² + ...

где g= 0.577216 ... — константа Эйлера. Для доста­точно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением

F_i -ln i+g+l

Среднее число пересылок Mavg в сортировке с вы­бором есть сумма Fi с i от 1 до n:

M_avg =n*(g+l)+(S_i : 1<i

Вновь аппроксимируя эту сумму дискретных членов интегралом Integral (1: п) ln x dx == x * (ln x— 1) == n * ln (п)— n + I

получаем, наконец, приблизительное значение M_avg = n(ln (n) + g)

Отсюда можно сделать заключение, что, как правило, алгоритм с прямым выбором предпочтительнее стро­гого включения. Однако, если ключи в начале упоря­дочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым.

2.3.2. Сортировка с помощью дерева

Метод сортировки с помощью прямого выбора ос­нован на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n —1 элемен­тов и т. д. Обнаружение наименьшего среди п эле­ментов требует—это очевидно — n — 1 сравнения, среди n — 1 уже нужно n — 2 сравнений и т. д. Сумма первых n — 1 целых равна 1/2*(n² — n). Как же в та­ком случае можно усовершенствовать упомянутый ме­тод сортировки? Этого можно добиться, только остав­ляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С по­мощью n/4 сравнений — меньший из пары уже вы­бранных меньших и т. д. Проделав n — 1 сравнений, мы можем построить дерево выбора вроде представ­ленного на рис. 2,3 и идентифицировать его корень как нужный нам наименьший ключ [2.21.

Второй этап сортировки — спуск вдоль пути, отме­ченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент (дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах (см. рис. 2.4 и 2.5). Элеме

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать