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

Сортирането чрез пряка селекция (метод на пряката селекция, на английски: selection sort) е един от простите алгоритми за сортиране.

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

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

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

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

Пример

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;

}