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

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

 

Основная идея метода состоит в том, чтобы идти по шагам 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

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