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

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

Алгоритъмът има сложност от Θ(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 22 $\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 = Θ(n²)

според формулата за сбор на аритметична прогресия. Всяко от тези n – 1 преминавания по масива изисква една размяна на елементи (последният елемент е вече на правилното място).

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

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

Сортирането чрез вмъкване прави средно два пъти по-малко сравнения от метода на прекия избор. Недостатък на последния метод е, че работи едно и също време независимо от подредбата на входния масив, дори когато той е предварително сортиран. Сортирането чрез вмъкване е по-адаптивно: то работи бързо, когато масивът е сортиран или почти сортиран.

Върху големи масиви методът на пряката селекция е доста по-бавен от сортирането чрез сливане и други бързи сортировки. Обаче сортирането чрез пряк избор и чрез вмъкване са по-бързи, когато работят върху малки масиви (до десет-двайсет елемента). Затова тези два метода се използват като дъно на някои рекурсивни сортировки, например бързото сортиране (quick sort).

Варианти

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

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

Понякога методът на коктейла се смята за двупосочен вариант на метода на мехурчето.

Сортирането чрез пряк избор е устойчива сортировка: при внимателно реализиране то не разменя елементи с равни ключове.

Пример

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 31 34	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;
}