Краткий обзор

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

Так уж складывается, профессиональные программисты редко используют основные алгоритмы сортировки, поэтому мы в настоящем курсе рассмотрим только один алгоритм. В пункте 4.1.3 Быстро сортирующие алгоритмы, мы исследуем алгоритм сортировки, который обычно быстрее чем все основные известные.

Selection Sort (Вид выбора)

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

Рисунок 1 Несортированный массив

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

Рисунок 2 Первая передача

После первой передачи самый маленький элемент помещается в первую позицию массива. Следующая передача, иллюстрированная рисунком 3, помещает второй самый маленький элемент во вторую позицию массива.

Рисунок 3 Вторая передача

Алгоритм selection sort всегда делает на одну передачу меньше чем в предыдущем шаге. Это - истина, даже если исходный массив уже сортируется. У алгоритма нет механизма, чтобы обнаружить случай, когда массив уже отсортирован, т.е. он работает до тех пор, пока не будут пересмотрены все элементы. Реализация кода selection sort в C++ представлен в листинге 1.