Сортиране по прост обмен

Предишен ◈ Следващото

От ляво на дясно последователно сравняване на две съседни елементи, и ако тяхната относителна позиция не съответства на състоянието на поръчката, след това те си разменят местата. След това, следното се вземат две съседни елементи и така нататък до края на масива.

След едно такова преминаване на последните N-та позиции на масива ще бъде максимум (или минимум), елементът ( "пусната" първи "балон"). Тъй като максималната (или минимум), елементът е вече в техните крайни позиции, след второто преминаване се извършва за обмен (п-1) -ти елемент. И така нататък. Общо изисква (п-1) подаване.

Задача. Диаграмата на бележника равенство на работата на алгоритъм произволно избрани масив.

Помислете за процедура, която изпълнява обсъдено по-горе алгоритъм:

Процедура Obmen (Var един масив 1.);
Var
I, J, F, G: цяло число;
започвам
защото: = п Downto 2 направи
за к: = 1 до I-1 направи
ако [й]> на [к + 1]
след това
започвам
F: = а [й];
на [й]: = а [к + 1];
на [к + 1]: = F;
приключи;
Край;

Задача. Направи едномерен масив програма за сортиране обсъжда метод.

Обмислете използването на рекурсия за изграждане на алгоритъм за сортиране на масив от стойности.

Алгоритъмът се прилага както следва: в централната сегмент на масива е избран (в средата) стойност; всички елементи на лявата страна на отсечката, надминавайки централната стойност, се движат от дясната страна, както и обратното. Следващата стъпка (който се използва за рекурсивно изисква същата процедура) алгоритъм се повтаря за двете части на сегмента.

Помислете процедура подредени по възходящ стойности на масива в обсег Massiv Left..Right индексите.

Процедура бързасортировка (ляво, дясно число ;. Massiv масив 1.);
Var
I, J, х, у. цяло число;
започвам
I: = наляво;
к: = десен;
х: = Massiv [(ляв + десен) DIV 2];<>
повторение
докато Massiv [Ь] Inc (I);
докато Massiv [й]> х направи
Декември (й);
ако аз<=j
след това
започвам
Y: = Massiv [Ь];
Massiv [Ь]: = Massiv [й];
Massiv [й]: = Y;
Inc (I);
Декември (й);
приключи;
докато> й;
ако Left след това
Quicksort (наляво, J);
ако аз след това
Бързасортировка (аз, надясно);
Край;

Свързани статии