На этом шаге мы рассмотрим этот метод сортировки.
- Определение.
- Сортировка выбором - это метод сортировки, при котором в неупорядоченной последовательности выбирается минимальный элемент, который исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную. Процесс повторяется до тех пор, пока все элементы не будут выбраны. Очевидно, что все выбранные элементы образуют упорядоченную последовательность.
Минимальный элемент, выбранный в исходной последовательности, может быть размещён на предназначенном ему месте упорядоченной последовательности несколькими способами. Рассмотрим два из них:
- (1) минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного списка, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого списка на единицу меньше размера предыдущего;
- (2) минимальный элемент после i-го просмотра перемещается на i-е место, i=1,2,3,..., другого специально созданного списка, а в исходном списке, на месте выбранного элемента размещается некоторое число, превосходящее по величине любой элемент сортируемого списка. Изменённый подобным образом список принимается за исходный, и осуществляется следующий просмотр.
На следующем шаге мы рассмотрим сортировку слиянием.
