Алгоритм selection sort является основным алгоритмом сортировки, который работает посредством итерации, или передачи сортируемых данных. Каждая передача приводит к перемещению одного элемента в его корректное расположение. В результате каждая последующая передача получает возможность исследовать на один элемент меньше чем предыдущая передача.
Рисунок 1 Несортированный массив
Рассмотрим несортированный массив, который содержит восемь элементов, поэтому selection sort должен будет сделать семь передач, чтобы отсортировать имеющиеся данные. Каждая передача помещает один элемент в правильную позицию. Первые два ячейки чисел представляют первые две передачи, соответственно. В каждой строке закрашенная стрелка указывает на позицию, которую передача стремится заполнить. Во время каждой передачи алгоритм ищет самый маленький остающийся элемент. Передача заканчивается алгоритмом, переставляющий самый маленький элемент в позицию закрашенной стрелки.
Рисунок 2 Первая передача
После первой передачи самый маленький элемент помещается в первую позицию массива. Следующая передача, иллюстрированная рисунком 3, помещает второй самый маленький элемент во вторую позицию массива.
Рисунок 3 Вторая передача
Алгоритм selection sort всегда делает на одну передачу меньше чем в предыдущем шаге. Это - истина, даже если исходный массив уже сортируется. У алгоритма нет механизма, чтобы обнаружить случай, когда массив уже отсортирован, т.е. он работает до тех пор, пока не будут пересмотрены все элементы. Реализация кода selection sort в C++ представлен в листинге 1.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: | // Sorting using selection sort template <typename T> void selection_sort(vector<T>& v) { for (unsigned int i = 0; i < v.size() - 1; i++) { unsigned int best = i; for (unsigned int j = i + 1; j < v.size(); j++) { if (v[j] < v[best]) { best = j; } } if (best != i) { T temp = v[i]; v[i] = v[best]; v[best] = temp; } } } |
| Listing 1Selection Sort |