Сортиране чрез пряка селекция - пряк избор
Съдържание
Сортиране е процес на нареждане елементи по определен признак. Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране чрез пряка селекция, прекия избор (selection sort) е един от основните методи за сортиране. Той е със сложност O(n^2).
Нека имаме редица с n броя елементи.Чрез този алгоритъм се обхожда редицата n–1 пъти и се поставя на "правилното" място всяка отделна стойност.
При алгоритъма на пряка селекция, последователните действия са:
(1) Избиране на минимална стойност като предварително се запомня мястото й в редицата (масива).
(2) Освобождаване на позицията, на която избраната стойност трябва да бъде записана.
(3) Записване на избраната стойност на полагаемото й се място.
Смяната на местата на отделните елементи се извършва посредством оператори за присвояване на стойност – най-често с трета – допълнителна променлива.
Ако има частично подредена редица алгоритъмът ще продължава проверката дори и всички елементи да са заели правилните си места. Това на практика довежда до продължаваща работа на алгоритъма без промяна наредбата на елементите. В случая е илюстрирано чрез повторение на последните 4 стъпки (7,8,9 и 10).
В описания по-долу пример е показан обратния случай - първо се нареждат най-големите елементи.
Начално състояние на редицата: 15;6;8;1;2;3;4;7;9;11
1-ви етап: 11;6;8;1;2;3;4;7;9;15
2-ри етап: 9;6;8;1;2;3;4;7;11;15
3-ти етап: 7;6;8;1;2;3;4;9;11;15
4-ти етап: 4;6;7;1;2;3;8;9;11;15
5-ти етап: 3;4;5;1;2;7;8;9;11;15
6-ти етап: 2;3;4;1;6;7;8;9;11;15
7-ми етап: 1;2;3;4;6;7;8;9;11;15
8-ми етап: 1;2;3;4;6;7;8;9;11;15
9-ти етап: 1;2;3;4;6;7;8;9;11;15
10-ти етап: 1;2;3;4;6;7;8;9;11;15
Търси се най-големият елемент и той си разменя мястото с последния елемент от редицата. Това продължава толкова пъти колкото са елементите в редицата
Следва код на примерна програма даваща решена задача с алгоритъм за сортиране по метод на пряка селекция - метод на прекия избор:
Имате предварително въведен едномерен масив с елементи от интервала [1..100]
Да се състави програма за сортиране на стойностите на масива чрез метода "сортиране чрез пряка селекция".
Пример: 15; 6; 8; 1; 2; 3; 4; 7; 9; 11;
Изход: 1; 2; 3; 4; 6; 7; 8; 9; 11; 15;
Блок схемата на алгоритъма за пряка селекция е в приложените електронни уроци.
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.