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

Сортування вибором полягає в тому, що спочатку в неупорядкованому| списку вибирається і відділяється|відокремлюється| від останніх най­менший| елемент. Після|потім| цього початковий|вихідний| список виявляється|опиняється| зміненим. Змінений список береться за початковий і процес продовжується|триває| до тих пір, поки всі елементи не будуть вибрані. Очевидно, що вибрані елементи утворюють впорядкований| список.

Наприклад, потрібно знайти мінімальний елемент списку:

{5, 11,6,4,9,2, 15,7}.

Процес вибору показаний на мал. 2.2, де в кожній строчці виписані порівнювані пари. Вибирані елементи з|із| мен­шим| вагою обведені кружком|гуртком|. Неважко бачити, що число порівнянь| відповідає на малюнку числу рядків, а число переміщень| — кількості змін вибраного елементу.

{5, 11, 6, 4, 9, 2, 15, 7}

Вибраний в початковому|вихідному| списку мінімальний елемент розміщується| на призначеному йому місці|місце-милі| декількома способами:

• мінімальний елемент після|потім| i-го| перегляду|проглядати| переміщається на i-е| місце|місце-милю| нового списку (i = 1, 2..., n), а в початковому|вихідному| списку на місце|місце-милю| вибраного елементу записується|занотовує| якесь| дуже велике число, що перевершує по величині будь-який елемент списку, при цьому довжина заданого списку залишається постійною. Змінений таким чином список можна приймати за початковий;

• мінімальний елемент записується на i-е місце початкового списку (i= 1, 2...., п), а елемент з i-го місця — на місце вибране. При цьому очевидно, що вже впорядковані елементи (а вони будуть розташовані зачинаючи з першого місця) виключаються з подальшого сортування, тому довжина кожного подальшого списку (списку, що бере участь в кожному подальшому перегляді) має бути на один елемент менше попереднього;

• вибраний мінімальний елемент, як і у попередньому випадку, переміщається на i-e місце заданого списку, а щоб це i-e місце звільнилося для запису чергового мінімального елементу, ліва від вибраного елементу частка списку переміщається управо на одну позицію так, щоб заповнилося місце, займане до цього вибраним елементом (елементи списку циклічно зрушуються).

Складність методу сортування вибором порядку складає 0(п²).

Дата добавления: 2013-12-14