Сортировка выбором
Сортировка выбором ( прямой выбор,линейный
выбор )
Согласно этому методу,начиная с первой записи таблицы, осуществляется
поиск элемента,имеющего наименьшее значение ключа. После
того, как этот элемент найден, он меняется местами с первой записью в
таблице. В результате такой перестановки запись с наименьшим значением
ключа помещается в первую позицию в таблице. Затем, начиная со второго
элемента таблицы, осуществляется поиск второго наименьшего ключа. Найденный
элемент меняется местами со вторым элементом таблицы. Этот процесс продолжается
до тех пор, пока все записи не будут расположены в порядке возрастания
кодов ключа. Число сравнений в данном методе равно n(n-1)/2 (в среднем
порядка n**2),где n - количество записей в таблице. Максимальное количество
перестановок при такой сортировке равно (n-1). В качестве примера рассмотрим
шаги алгоритма для таблицы со следующими значениями ключей:
23 11 4
56 9 35
7
Таблица на различных этапах упорядочения (подчеркнуты перемещаемые элементы)
:
23 11 4
56 9 35
7
~~~ ~~~
4 11 23
56 9 35
7
~~~
~~~
4 7 23
56 9 35
11
~~~ ~~~
4 7 9
56 23 35 11
~~~
~~~~
4 7 9
11 23 35 56
~~~
Линейный выбор с подсчетом
При упорядочении таблицы этим методом необходима память для хранения исходной
и упорядоченной таблиц,а также дополнительно должна быть выделена память
под счетчик для каждой записи таблицы.
Просмотр таблицы начинается с первой записи. Ее ключ сравнивается с ключами
последующих записей.При этом счетчик большего из сравниваемых ключей увеличивается
на 1. При втором просмотре таблицы первый ключ уже не рассматривается,второй
ключ сравнивается со всеми последующими.Результаты сравнений фиксируются
в счетчиках. Для таблицы,содержащей n элементов,этот процесс повторяется
n-1 раз.
После выполнения всех просмотров счетчик каждого элемента указывает, какое
количество ключей таблицы меньше ключа этого элемента.Эти счетчики используются
затем в качестве индексов элементов результирующей таблицы. Поместив записи
в результирующую таблицу в соответствии со значениями их счетчиков ,получим
упорядоченную таблицу. Выполняется n-1 просмотров с n/2 сравнениями в
среднем при
каждом просмотре.Значения счетчиков изменяются столько
раз,сколько выполняется сравнений.
Число пересылок равно n.
Рассмотрим пример использования этого метода.
Исходная таблица и массив счетчиков:
--------------T-----------T----------¬
¦ индексы ¦ ключи
¦ счетчики ¦
+-------------+-----------+----------+
¦ 0
¦ 9
¦
0 ¦
¦ 1
¦ 5
¦
0 ¦
¦ 2
¦ 10
¦
0 ¦
¦ 3
¦ 2
¦
0 ¦
L-------------+-----------+-----------
Рассмотрим изменение массива счетчиков в результате просмотров:
1-й 2-й 3-й Результирующая таблица
(ключи):
2 2 2
2
0 1 1
5
1 2 3
9
0 0 0
10
