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

Сравнить эффективность методов сортировки массивов:

Метод прямого выбора и метод сортировки с помощью дерева.

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

Этот прием основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом ai.

Возможно вы искали - Реферат: Сравнительная характеристика инструментов для web-дизайна

3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1, приведен в табл. 2.2. Алгоритм формулируется так:

FORi:=ITO n-1 DO

присвоить k индекс наименьшего из a[i],,, a[nJ; поменять местами a[i] и a[j] ;

end

Похожий материал - Реферат: Linux, FreeBSD и другие

Такой метод – его называют прямым выбором – в не­котором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматри­ваются только один очередной элемент исходной последовательности и все элементы готовой последо­вательности, среди которых отыскивается точка вклю­чения; при прямом выборе для поиска одного эле­мента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую после­довательность. Полностью алгоритм прямого выбора приводится в прогр. 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

Похожий материал - Реферат: Сравнительный анализ языков программирования JavaScript и VBScript

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

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

с = (n² - n)/2

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