Сортировка методом прямого выбора
Суть метода заключается в следующем. Выбирается наименьший элемент в "оставшейся" (неотсортированной) части и меняется местами с первым элементом (в этой же неотсортированной части). После этого длина неотсортированной части уменьшается на один элемент (на первый), и весь процесс продолжается уже с (n – 1) элементами, затем с (n – 2) элементами и т.д., до тех пор, пока не останется один, самый большой элемент.
Этот метод в некотором смысле противоположен методу прямого включения. В методе прямого включения на каждом шаге рассматривается только один очередной элемент и все элементы уже "готовой" части последовательности, среди которых отыскивается точка включения этого очередного элемента. А в методе прямого выбора для поиска одного (минимального) элемента просматривают все элементы неотсортированной части, и этот минимальный элемент помещается как очередной элемент в уже "готовую" часть.
Текстовый алгоритм метода:
1. Начало.
2. Выполнить цикл, пока i имеет значения от 1 до N – 1, шаг = 1:
а) поместим текущий (i-ый) элемент в какую-нибудь ячейку памяти (Х) и запомним порядковый номер (i) текущего элемента (в переменной К);
б) выполнить цикл, пока j имеет значения от i + 1 (то есть от следующего за i элемента) до N, шаг = +1:
тело цикла: если Х > А(j), то помещаем в ячейку Х элемент А(j) и запоминаем его номер в ячейке К;
в) присвоить А(К) = А(i) и А(i) = Х.
3. Конец.
На рис. 3 приведен пример выполнения сортировки методом прямого выбора.
Исходная последовательность |
44 |
55 |
12 |
42 |
94 |
18 |
06 |
67 |
I = 1 |
06 |
55 |
12 |
42 |
94 |
18 |
44 |
67 |
I = 2 |
06 |
12 |
55 |
42 |
94 |
18 |
44 |
67 |
I = 3 |
06 |
12 |
18 |
42 |
94 |
55 |
44 |
67 |
I = 4 |
06 |
12 |
18 |
42 |
94 |
55 |
44 |
67 |
I = 5 |
06 |
12 |
18 |
42 |
44 |
55 |
94 |
67 |
I = 6 |
06 |
12 |
18 |
42 |
44 |
55 |
94 |
67 |
I = 7 |
06 |
12 |
18 |
42 |
44 |
55 |
67 |
94 |
Рис. 3. Пример сортировки методом прямого выбора
На рисунке 4 приведена блок-схема сортировки методом прямого выбора.
Рис. 4. Блок-схема сортировки методом прямого выбора
Сортировка прямым выбором подходит для случая, когда все данные находятся в памяти, а отсортированные данные последовательно выводятся.