Разлика между версии на „Сортиране чрез пряка селекция“

 
== Пример стъпка по стъпка ==
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни. <br />
Първо преминаване <br />
'''64''' '''25''' 12 22 11 <math>\to</math> '''25''' '''64''' 12 22 11 <br />
'''25''' 64 '''12''' 22 11 <math>\to</math> '''12''' 64 '''25''' 22 11 <br />
12 64 25 22 11 <math>\to</math> 12 64 25 22 11 <br />
'''12''' 64 25 22 '''11''' <math>\to</math> '''11''' 64 25 22 '''12''' <br />
След първото преминаваме на първа позиция е най-малкият елемент от масива.
 
<br />Първо преминаване:<br />'''64''' '''25''' 12 22 11 <math>\to</math> '''25''' '''64''' 12 22 11 <br />'''25''' 64 '''12''' 22 11 <math>\to</math> '''12''' 64 '''25''' 22 11 <br />12 64 25 22 11 <math>\to</math> 12 64 25 22 11 <br />'''12''' 64 25 22 '''11''' <math>\to</math> '''11''' 64 25 22 '''12''' <br />След първото преминаване най-малкият елемент на масива се намира на първа позиция.
Второ преминаване <br />
 
ПървоВторо преминаване <br />:
11 '''64''' '''25''' 22 12 <math>\to</math> 11 '''25''' '''64''' 22 12 <br />
11 '''25''' 64 '''22''' 12 <math>\to</math> 11 '''22''' 64 '''25''' 12 <br />
11 '''22''' 64 25 '''12''' <math>\to</math> 11 '''12''' 64 25 '''22''' <br />
 
11 '''64''' '''25''' 22 12 <math>\to</math> 11 '''25''' '''64''' 22 12 <br />11 '''25''' 64 '''22''' 12 <math>\to</math> 11 '''22''' 64 '''25''' 12 <br />11 '''22''' 64 25 '''12''' <math>\to</math> 11 '''12''' 64 25 '''22''' <br />Трето преминаване:<br />11 12 '''64''' '''25''' 22 <math>\to</math> 11 12 '''25''' '''64''' 22 <br />11 12 '''25''' 64 '''22''' <math>\to</math> 11 12 '''22''' 64 '''25''' <br />Четвърто преминаване:<br />11 12 22 '''64''' '''25''' <math>\to</math> 11 12 22 '''25''' '''64''' <br />
Трето преминаване <br />
11 12 '''64''' '''25''' 22 <math>\to</math> 11 12 '''25''' '''64''' 22 <br />
11 12 '''25''' 64 '''22''' <math>\to</math> 11 12 '''22''' 64 '''25''' <br />
 
Четвърто преминаване <br />
11 12 22 '''64''' '''25''' <math>\to</math> 11 12 22 '''25''' '''64''' <br />
 
== Анализ ==
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми. За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи (това отнема ''n'' – 1 сравнения) и след това да го разменим с първата позиция. За да намерим следващият най-малък елемент се изисква да сканираме оставащите ''n'' – 1 елементи и така нататък,. Общият брой сравнения е равен на
 
за (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) сравнения (виж аритметична прогресия). Всяко от тези сканирания изисква 1 разменяне за n-1 елементи
(''n'' − 1) + (''n'' − 2) + ... + 2 + 1 = ''n''(''n'' − 1) / 2 = Θ(''n''<sup>2</sup>)
(последният елемент е вече на правилното място)
 
според формулата за сбор на аритметична прогресия. Всяко от тези ''n'' – 1 преминавания по масива изисква една размяна на елементи (последният елемент е вече на правилното място).
 
== Сравнение с други алгоритми за сортиране ==
Методът на прекия избор почти винаги е по-бърз от метода на мехурчето и метода на гнома. Сортирането чрез вмъкване и чрез пряка селекция си приличат по това, че след ''k''-тата итерация първите k елемента на масива са подредени във възходящ ред. Предимството на метода на вмъкването е, че проверява толкова елемента, колкото му е нужно, за да сложи (''k'' + 1)-ия елемент на мястото му, докато методът на пряката селекция трябва да провери всички останали елементи, за да намери (''k'' + 1)-ия елемент.
Спрямо други прости Θ(n2) алгоритми, методът на пряката селекция почти винаги е по-бърз от метода на мехурчето и метода на гнома(gnome sort). Методът на
вмъкването е много подобен в това, че след k-та итерация, първите k елемента в масива са в сортиран ред. Предимството на метода на вмъкването е, че сканира
толкова елемента колкото му е нужно за да сложи k + 1 елемент на мястото му, докато методът на пряката селекция трябва да сканира всички останали елементи
за да намери k + 1 елемент.
 
Сортирането чрез вмъкване прави средно два пъти по-малко сравнения от метода на прекия избор. Недостатък на последния метод е, че работи едно и също време независимо от подредбата на входния масив, дори когато той е предварително сортиран. Сортирането чрез вмъкване е по-адаптивно: то работи бързо, когато масивът е сортиран или почти сортиран.
Прости сметки показват, че следователно на метода на вмъкването ще са му нужни 2 пъти по-малко сравнения спрямо метода на пряката селекция. Може да се
разглежда като предимство за някои real-time апликации, че методът на пряката селекция ще работи идентично без значение от реда на масива, докато времето,
за което ще работи методът на вмъкването може да варира значително. Обаче, в повечето случаи това може да се разглежда като предимство за метода на
вмъкването, защото работи много по-ефикасно, ако масивът е сортиран или „близо до сортиран“.
 
Върху големи масиви методът на пряката селекция е доста по-бавен от сортирането чрез сливане и други бързи сортировки. Обаче сортирането чрез пряк избор и чрез вмъкване са по-бързи, когато работят върху малки масиви (до десет-двайсет елемента). Затова тези два метода се използват като дъно на някои рекурсивни сортировки, например бързото сортиране (quick sort).
Накрая, методът на пряката селекция е доста по-малко производителен върху големи масиви от Θ(n log n) разделяй-и-владей алгоритми като метода на сливане
(merge sort). Обаче методът на пряката селекция и методът на вмъкване са по-бързи, когато работят върху малки масиви (10 – 20 елемента). Полезна оптимизация
в практиката за рекурсивните алгоритми е да се смени към метода на вмъкване или метода на пряката селекция, когато елементите от несортирания масив станат
по-малко от 20.
 
== Варианти ==
HeapsortПирамидалното сортиране (heap sort) значително подобряваускорява метода на пряката селекция катос използвапомощта скритана специална структура от данни, наречена пирамида (heap). заТя да забързапозволява намирането и премахването на най-малката данна. Ако е имплементиран коректно, heap-а ще позволи намиранетоизтриването на следващия най-малък елемент с Θ(log n) стъпки вместо Θ(n).
 
Двупосочен вариант на метода на пряката селекция, наричан още методаметод на коктейла (cocktail sort), е алгоритъм, който при всяко преминаване през масива намира едновременно най-малкиятмалкия и най-големия от останалите елементи. Това намалява броя на преминаванията, но не и броя на сравненията и размените.
най-големият елемент в колекцията при всяко преминаване. Това намалява броя на сканиранията, но всъщност не намалява броя на сравненията или разменянията.
 
Все пак,Понякога методът на коктейла(cocktail sort) по-честосе спадасмята катоза двупосочен вариант на метода на мехурчето.
 
Сортирането чрез пряк избор е устойчива сортировка: при внимателно реализиране то не разменя елементи с равни ключове.
Методът на пряката селекция може да бъде имплементиран като стабилен сортиращ алгоритъм. Вместо да разменяме във втора стъпка, можем да вкараме минималната
стойност на първа позиция. По този начин алгоритмът ни е стабилен. Обаче, за да е възможна тази модификация, на нас ни е нужна структура от данни, която да
поддържа ефикасно вмъкване и изтриване, като например свързан списък, иначе води до Θ(n2) сложност.
 
== Пример ==
| bgcolor="lightblue" |31||34||12||22|| bgcolor="pink" |11
|}
|| Най-малкият елемент е 11. Разменят се местата на 11 и 31.
|-
|
| |11|| bgcolor="lightblue" |34|| bgcolor="pink" |12||22||31
|}
|| Най-малкият оставащ елемент от останалия списък е 12. Разменят се местата на 12 и 34.
|-
|
| |11||12|| bgcolor="lightblue" |34|| bgcolor="pink" |22||31
|}
|| Вече имаме една част от списъка, която е сортирана. РазменятСега се местата наразменят 22 и 34.
|-
|
| |11||12||22|| bgcolor="lightblue" |34|| bgcolor="pink" |31
|}
|| Разменят се местата на 31 и 34.
|-
|
|}
 
== Пример на C# за сортиране на числата,числа чрезпо алгоритъмаметода на прякатапрекия селекцияизбор ==
<pre>
using System;
</pre>
 
== Пример на C++ за сортиране на числата,числа чрезпо алгоритъмаметода на прякатапрекия селекцияизбор ==
<code><pre>#include <iostream>
using namespace std;
 
}</pre>
 
[[Категория:Алгоритми]]
Анонимен потребител