Программы •Железо • Драйверы • Хостинг •Энциклопедия рекламы

     Сортировка выбором

    Сортировка выбором ( прямой выбор,линейный выбор )

Согласно этому методу,начиная с первой записи таблицы, осуществляется поиск элемента,имеющего наименьшее значение ключа. После    того, как этот элемент найден, он меняется местами с первой записью в таблице. В результате такой перестановки запись с наименьшим значением ключа помещается в первую позицию в таблице. Затем, начиная со второго элемента таблицы, осуществляется поиск второго наименьшего ключа. Найденный элемент меняется местами со вторым элементом таблицы. Этот процесс продолжается до тех пор, пока все записи не будут расположены в порядке возрастания кодов ключа. Число сравнений в данном методе равно 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