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

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

1 шаг:

min

2 шаг:

min

3 шаг:

min

4 шаг:

min

5 шаг:

min

6 шаг:

min

7 шаг:

min

Результат:

 

БЛОК – СХЕМА

 

I = 1

 

Æ 1

 

J = I L = 1

 

 

Æ 1

 

R = A(L) F(L) =A(I) A(I) = R

1 Æ

 

 

L = J

 

 

 

J = J + 1

I = I + 1

 

 

Программа реализующая метод выбора, будет иметь следующий вид:

Rem Selection Sort

Const n=20 ‘длина массива

Dim Vector (1 to n)

defsng Min

defint Imin, S, i

Cls

print “введите элементы массива:”

for i = 1 to n

input Vector (i)

next

for S=1 to n-1

‘поиск минимального элемента в диапазоне от S-го элемента до n-го

Min = Vector (S)

Imin = S

For i = S+1 to n

If Vector(i) < Min then Min = Vector (i): Imin = I

next

Vector [Imin]: = Vector [S]:next ’обмен местами минимального и S-го элемента

Print “Отсортированный массив:”

For i: = 1 to n

Print Vector (i);

next

Результат работы:

Bведите элементы массива: 7 6 5 4 0 9 8 3 2 1 Отсортированный массив: 0 1 2 3 4 5 6 7 8 9

4.2.2.5.3. Сортировка обменом («пузырьковая сортировка»)

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются. Далее берутся два следующих соседних элемента и так далее до конца массива. После одного такого прохода на последний n-ой позиции массива будет стоять максимальный элемент («всплыл первый пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1 элемента. И так далее. Всего требуется n-1 проход.

1 шаг:

3 11

7 11 2 11 9 11

2 шаг: 1 11 4 11

5

3 5 1 7

4 7

3 шаг: 2 7

1 5

4 5

4 шаг: 2 5

1 3 2 4

5 шаг:

1

2 3

6 шаг:

7 шаг:

 

Результат:

 

БЛОК – СХЕМА

	I = 2

 

 

Æ 1

 

K = M

 

 

Æ 1

 

I = I + 1

1 Æ

R = A(K-1) A(K-1)=A(K) A(K) = R

 

 

 

K = K-1

 

 

 

Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:

rem Duddle Sort

Const N = 20 ‘ длина массива

Dim Vector(1 to n)

Def sng B

defint i, K

Cls

Print “введите элементы массива:”

for i: = 1 to n

input Vector (i)

next

for K = n to 2 step -1

‘всплывание” очередного максимального элемента

{на К-ю позицию}

for i: = 1 to K-1 do

if Vector (i) > Vector (i+1) then

B: = Vector (i]): Vector (i) = Vector (i+1): Vector {i+1) = B

End;

‘отсортированный массив

For i = 1 to n

Print Vector (i)

next

print

Результат работы:

Bведите элементы массива: 7 6 5 4 0 9 8 3 2 1 Отсортированный массив: 0 1 2 3 4 5 6 7 8 9