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

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 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

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

Program Selection Sort;

Uses Crt;

const

n=20; { длина массива}

typc

TVector = array [1…n] of Real;

Var

Vector: TVector;

Min: Real;

Imin, S: Integer;

i: Integer;

Begin

Clr Srt:

Writeln (‘введите элементы массива:’);

for i: = 1 to n do Read (Vector [i]); Readln;

{ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }

for S:=1 to n-1 do

begin

{поиск минимального элемента в диапазоне от }

{S-го элемента до n-го}

Min: = Vector [S];

I min: = S;

For i: = S+1 to n do

If Vector [i] < Min then

begin

Min: = Vector [i];

I min: = I;

End;

{обмен местами минимального и S-го элемента}

Vector [Imin]: = Vector [S];

Vector [S]: = Min;

End;

{ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }

Writeln (‘Отсортированный массив:’);

For i: = 1 to n do Write (Vector [i]: 8: 2);

Writeln;

End.

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

Bведите элементы массива: Отсортированный массив:

5.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

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

Program Duddle Sort;

Uses Crt;

Const

N = 20; { длина массива}

Type

TVector = array [1…n] of Real;

Var

Vector: Tvector;

B: Real;

i, K: Integer;

begin

ClrScr;

Writeln (‘введите элементы массива:’);

for i: = 1 to n do Read (Vector [i]); Readln;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }

for K: = n downto 2 do

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

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

for i: = 1 to K-1 do

if Vector [i] > Vector [i+1] then

begin

B: = Vector [i];

Vector [i]: = Vector [i+1];

Vector [i+1]: = B;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }

Writeln (‘отсортированный массив:’);

For i: = 1 to n do Write (‘Vector [i]: 8: 2’);

Writeln;

End.

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

Bведите элементы массива: Отсортированный массив: