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

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

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

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

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

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)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--