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

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

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

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

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

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

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

Нека имаме масив със следните елементи: 64,25,12,22,11и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни. 64,25,12,22,11 $\to$ 11 25 12 22 64 -> намираме най-малкия елемент и го слагаме на първа позиция
11 25 12 22 64 $\to$ 11 12 25 22 64 започваме от втория елемент, защото първият е вече сортиран и на второ място идва вторият най-малък елемент - малко по малко ги сортираме
11 12 25 22 64 $\to$ 11 12 22 25 64 започваме от третият елемент и сравняваме с останалата част
11 12 22 25 64 $\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 елементи (последният елемент е вече на правилното място)

Пример

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++

#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;

}