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

Основная идея метода состоит в том, чтобы идти по шагам j=1, 2,..., N-1, находя на j -м шаге среди неотсортированных записей запись с наименьшим ключом, и каким-либо образом помещать ее на соответствующее место.

К методам сортировки посредством выбора относятся следующие:

простой линейный выбор, квадратичный выбор, линейный выбор с

обменом, турнир с выбыванием, пирамидальная сортировка и др.,

различающиеся способами выбора очередности сравнений и обмена.

а) простой линейный выбор (монеты, структурограмма, пример)

б) линейный выбор с обменом

Простой линейный выбор (монеты, структурограмма, пример)

	Обмен: X(I)< -> X(J)

5, 4, 1, 2, 3

J=1, I=2;

4 5 1 2 3

I=3;

1 5 4 2 3

I=4;

1 5 4 2 3

I=5;

1 5 4 2 3

J=2, I=3;

1 4 5 2 3

I=4;

1 2 5 4 3

I=5;

1 2 5 4 3

J=3, I=4;

1 2 4 5 3

I=5;

1 2 3 5 4

J=4, I=5;

1, 2, 3, 4, 5

Метод медленный т.к. очень много обменов.

Число сравнений = N*(N-1)/2

Число обменов

Минимальное =0

Максимальное = 2*N