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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

Принцип на действие[редактиране | edit source]

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

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

Пример стъпка по стъпка[редактиране | edit source]

Нека имаме масив със следните елементи: 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

Анализ[редактиране | edit source]

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

Сравнение с други алгоритми за сортиране[редактиране | edit source]

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

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

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

Варианти[редактиране | edit source]

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

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

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

Пример[редактиране | edit source]

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# за сортиране на числата, чрез алгоритъма на пряката селекция[редактиране | edit source]

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++ за сортиране на числата, чрез алгоритъма на пряката селекция[редактиране | edit source]

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

}