Сортування прямим вибором

Алгоритм сортування прямим вибором у сенсі протилежний сортуванню прямими включеннями.

При прямому включенні кожному кроці розглядається лише одне черговий елемент вхідний послідовності і всі елементи готової послідовності знаходження місця включення.

При прямому виборі для пошуку одного елемента з найменшим ключем проглядаються всі елементи вхідної послідовності і знайдений елемент міститься як черговий елемент на кінець готової послідовності.

  • прямим

    • Метод сортування прямим вибором ґрунтується на наступних правилах:

    • Вибирається елемент із найменшим ключем.
    • Він змінюється місцями із першим елементомa0.
    • Потім ці операції повторюються з елементами, що залишилисяn-1,n-2 елементами і так далі до тих пір, поки не залишиться один, найбільший елемент.

    вибором
    Реалізація сортування прямим вибором на Сі

    Аналіз алгоритму прямим вибором

    Число порівнянь ключів не залежить від порядку ключів:

    C=½(n 2 -n).

    Число перестановок мінімальне

    Mmin=3(n-1)

    у разі спочатку впорядкованих ключів та максимально

    Mmax= n2/4 +3(n-1),

    якщо спочатку ключі розташовуються у зворотному порядку.

    Середня кількість пересилок

    Mср≈n(ln n + g),

    деg = 0,577216... - Константа Ейлера.

    Резюме : як правило, сортування прямим вибором краще алгоритму прямого включення, однак, якщо ключі на початку впорядковані або майже впорядковані, пряме включення залишатиметься дещо швидшим.