Сортиране чрез пряка селекция

В компютърните науки методът на пряката селекция (Шаблон:Lang-en) е алгоритъм за сортиране. Той е един от фундаменталните методи за сортиране и е прост и лесен на имплементиране.

Алгоритъмът има сложност от Θ(n²), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за сортиране чрез вмъкване (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.

Принцип на действие

Алгоритъмът работи по следния начин:

1. Намира най-малкия елемент в списъка като сравнява първият елемент с всички останали
2. Разменя го с елемента на първа позиция
3. Повтаря горните две стъпки за всеки следващ елемент

Пример стъпка по стъпка

Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни.
Първо преминаване
64 25 12 22 11 $\to$ 25 64 12 22 11
25 64 12 22 11 $\to$ 12 64 25 22 11
12 64 25 22 11 $\to$ 12 64 25 22 11
12 64 25 22 11 $\to$ 11 64 25 22 12
След първото преминаваме на първа позиция е най-малкият елемент от масива.

Второ преминаваме

11 64 25 22 12 $\to$ 11 25 64 22 12
11 25 64 22 12 $\to$ 11 22 64 25 12
11 22 64 25 12 $\to$ 11 12 64 25 22

Трето преминаваме
11 12 64 25 25 $\to$ 11 12 25 64 22
11 12 25 64 22 $\to$ 11 12 22 64 25

Четвърто преминаваме
11 12 22 64 25 $\to$ 11 12 22 25 64

Анализ

Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми. За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи (това отнема n – 1 сравнения) и след това да го разменим с първата позиция. За да намерим следващият най-малък елемент се изисква да сканираме оставащите n – 1 елементи и така нататък, за (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) сравнения (виж аритметична прогресия). Всяко от тези сканирания изисква 1 разменяне за n-1 елементи (последният елемент е вече на правилното място)

Сравнение с други алгоритми за сортиране

Спрямо други прости Θ(n2) алгоритми, методът на пряката селекция почти винаги е по-бърз от метода на мехурчето и метода на гнома(gnome sort). Методът на вмъкването е много подобен в това, че след k-та итерация, първите k елемента в масива са в сортиран ред. Предимството на метода на вмъкването е, че сканира толкова елемента колкото му е нужно за да сложи k + 1 елемент на мястото му, докато методът на пряката селекция трябва да сканира всички останали елементи за да намери k + 1 елемент.

Прости сметки показват, че следователно на метода на вмъкването ще са му нужни 2 пъти по-малко сравнения спрямо метода на пряката селекция. Може да се разглежда като предимство за някои real-time апликации, че методът на пряката селекция ще работи идентично без значение от реда на масива, докато времето, за което ще работи методът на вмъкването може да варира значително. Обаче, в повечето случаи това може да се разглежда като предимство за метода на вмъкването, защото работи много по-ефикасно, ако масивът е сортиран или „близо до сортиран“.

Накрая, методът е пряката селекция е доста по-малко производителен върху големи масиви от Θ(n log n) разделяй-и-владей алгоритми като метода на сливане (merge sort). Обаче методът на пряката селекция и методът на вмъкване са по-бързи, когато работят върху малки масиви (10 – 20 елемента). Полезна оптимизация в практиката за рекурсивните алгоритми е да се смени към метода на вмъкване или метода на пряката селекция, когато елементите от несортирания масив станат по-малко от 20.

Варианти

Heapsort значително подобрява метода на пряката селекция като използва скрита структура от данни heap за да забърза намирането и премахването на най-малката данна. Ако е имплементиран коректно, heap-а ще позволи намирането на следващия най-малък елемент с Θ(log n) стъпки вместо Θ(n).

Двупосочен вариант на метода на пряката селекция, наричан още метода на коктейла(cocktail sort), е алгоритъм, който намира едновременно най-малкият и най-големият елемент в колекцията при всяко преминаване. Това намалява броя на сканиранията, но всъщност не намалява броя на сравненията или разменянията.

Все пак, методът на коктейла(cocktail sort) по-често спада като двупосочен вариант на метода на мехурчето.

Методът на пряката селекция може да бъде имплементиран като стабилен сортиращ алгоритъм. Вместо да разменяме във втора стъпка, можем да вкараме минималната стойност на първа позиция. По този начин алгоритмът ни е стабилен. Обаче, за да е възможна тази модификация, на нас ни е нужна структура от данни, която да поддържа ефикасно вмъкване и изтриване, като например свързан списък, иначе води до Θ(n2) сложност.

Пример

31 34 12 22 11	Най-малкият елемент е 11. Разменят се местата на 11 и 31.
11 34 12 22 31	Най-малкият елемент от останалия списък е 12. Разменят се местата на 12 и 34.
11 12 34 22 31	Вече имаме една част от списъка, която е сортирана. Разменят се местата на 22 и 34.
11 12 22 34 31	Разменят се местата на 31 и 34.
11 12 22 31 34	Списъкът е сортиран

Пример на C# за сортиране на числата, чрез алгоритъма на пряката селекция

using System;
class SelectionSort
{
    static void Main()
    {

        int[] array = new int[] { 64, 25, 12, 22, 11 };
        for (int i = 0; i < array.Length - 1; i++)
        {
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[i] > array[j]) // swap items
                {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
        for (int i = 0; i < array.Length; i++) // print sorted array
        {
            Console.Write(array[i] + " ");
        }
    }
}

Пример на C++ за сортиране на числата, чрез алгоритъма на пряката селекция

#include <iostream>
using namespace std;

int main()
{
	int array[5]={31,34,12,22,11};
	for(int i=0; i<5; ++i)
	{
		int min = i;
		for(int j=i; j<5; ++j)
		if(array[min]>array[j])
		min = j;

		swap(array[min],array[i]);
	}

	for(int i=0; i<5; i++)
	cout << array[i] << "\t";
	return 0;

}