Сортировка простым выбором

18,6,12,42,94,55,44,67

44,55,12,42,94,6,18, 67

Пока не возникнет сравнение среднего элемента, то есть деление последовательностей будет завершено.

Первый же просмотр обеспечил распределение элементов в последовательности таким образом, что слева находятся все числа, меньшие X, а справ все элементы большие X. Между собой элементы не упорядочены, что можно увидеть на числовом примере. Просмотр правой и левой подпоследовательностей продолжается до тех пор,

Пример:

i=1 j=8

<42 >42

i=2 j=7

Далее то же самое выполняется внутри для каждой из подпоследовательностей. Длина каждой из подпоследовательностей уменьшается, пока не дойдем до 1-ого элемента в последовательности. Быстрая сортировка является очень удобной для рекурсивного описания процесса сортировки, так как для каждой из подпоследовательностей изменяется только размерность, а принцип остается неизменным.

Выбирается из последовательности наименьшей элемент или элемент с наименьшим ключом. Он отправляется на место первого элемента. Остальные элементы местами не меняются. (рис. 3)
C=1/2(n²-n) Mmin = 3(n-1), a

Mmax=trunc(n²/4)+3(n-1);

Среднее число перестановок определяется через эйлерову константу Y=0.577216…

M_cp=N*(lnN+Y)

Пример:10,8,5
i:=1 n:=3 1 < 2 … k:=1 x:=10 j:=2 2 <3.. 8<10… k:=2 x:=8;

j:=3 3 < 3.. 5<8.. k:=3 x:=5
j:=4.. 4>3 a[3]:=10; a[1]:=5;

i:=2 2 < 2 … k:=2 x:=8; j:=3 3 < 3…10>8 j:=4.. 4>3 a[2]:=a[2];

a[2]:=8; …. i:=3;

3>2 … 5,8,10

Рис. 3

Дата добавления: 2014-01-15