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

 

Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве. Далее, находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.

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

 

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

S

O

R

T

I

N

G

E

X

A

M

P

L

E

A

A

O

R

T

I

N

G

E

X

S

M

P

L

E

A

A

E

R

T

I

N

G

O

X

S

M

P

L

E

A

A

E

R

T

I

N

G

O

X

S

M

P

L

E

A

A

E

E

T

I

N

G

O

X

S

M

P

L

R

A

A

E

E

G

I

N

T

O

X

S

M

P

L

R

A

A

E

E

G

I

N

T

O

X

S

M

P

L

R

A

A

E

E

G

I

L

T

O

X

S

M

P

N

R

A

A

E

E

G

I

L

M

O

X

S

T

P

N

R

A

A

E

E

G

I

L

M

N

X

S

T

P

O

R

A

A

E

E

G

I

L

M

N

O

S

T

P

X

R

A

A

E

E

G

I

L

M

N

O

P

T

S

X

R

A

A

E

E

G

I

L

M

N

O

P

R

S

X

T

A

A

E

E

G

I

L

M

N

O

P

R

S

X

T

A

A

E

E

G

I

L

M

N

O

P

R

S

T

X

A

A

E

E

G

I

L

M

N

O

P

R

S

T

X

Рис.1. Пример работа сортировки выбором

 

В этом примере первый проход не дал результата, поскольку слева от А в массиве нет элемента, меньшего А. На втором проходе другой элемент А оказался наименьшим среди оставшихся, поэтому он меняется местами с элементом S, занимающим вторую позицию. Далее, на третьем проходе, элемент Е, находящийся в середине массива, меняется местами с О, занимающим третью позицию; затем, на четвертом проходе, еще один элемент Е меняется местами с R, занимающим четвертую позицию и т.д.

Для каждого i от I до г-1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],...,a[r],. По мере продвижения индекса i слева направо, элементы слева от него занимают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.

Недостаток сортировки выбором заключается в том, что время ее выполнения лишь в малой степени зависит от того, насколько упорядочен исходный массив. Процесс нахождения минимального элемента за один проход массив дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого массива. На сортировку почти отсортированного массива требуется столько же времени, сколько и на сортировку массива, упорядоченного случайным образом!