Сортиране чрез пряка селекция: Разлика между версии
Ред 10: | Ред 10: | ||
== Пример стъпка по стъпка == |
== Пример стъпка по стъпка == |
||
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни. |
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни. |
||
⚫ | |||
'''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 /> |
|||
⚫ | |||
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 на брой елементи (това отнема ''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. |
|||
== Варианти == |
== Варианти == |
||
Пирамидалното сортиране (heap sort) значително ускорява метода на пряката селекция с помощта на специална структура от данни, наречена пирамида (heap). Тя позволява намирането и изтриването на следващия най-малък елемент с Θ(log n) стъпки вместо Θ(n). |
|||
Двупосочен вариант на метода на пряката селекция, наричан още |
Двупосочен вариант на метода на пряката селекция, наричан още метод на коктейла (cocktail sort), е алгоритъм, който при всяко преминаване през масива намира едновременно най-малкия и най-големия от останалите елементи. Това намалява броя на преминаванията, но не и броя на сравненията и размените. |
||
най-големият елемент в колекцията при всяко преминаване. Това намалява броя на сканиранията, но всъщност не намалява броя на сравненията или разменянията. |
|||
Понякога методът на коктейла се смята за двупосочен вариант на метода на мехурчето. |
|||
Сортирането чрез пряк избор е устойчива сортировка: при внимателно реализиране то не разменя елементи с равни ключове. |
|||
Методът на пряката селекция може да бъде имплементиран като стабилен сортиращ алгоритъм. Вместо да разменяме във втора стъпка, можем да вкараме минималната |
|||
стойност на първа позиция. По този начин алгоритмът ни е стабилен. Обаче, за да е възможна тази модификация, на нас ни е нужна структура от данни, която да |
|||
поддържа ефикасно вмъкване и изтриване, като например свързан списък, иначе води до Θ(n2) сложност. |
|||
== Пример == |
== Пример == |
||
Ред 71: | Ред 48: | ||
| bgcolor="lightblue" |31||34||12||22|| bgcolor="pink" |11 |
| bgcolor="lightblue" |31||34||12||22|| bgcolor="pink" |11 |
||
|} |
|} |
||
|| Най-малкият елемент е 11. Разменят се |
|| Най-малкият елемент е 11. Разменят се 11 и 31. |
||
|- |
|- |
||
| |
| |
||
Ред 77: | Ред 54: | ||
| |11|| bgcolor="lightblue" |34|| bgcolor="pink" |12||22||31 |
| |11|| bgcolor="lightblue" |34|| bgcolor="pink" |12||22||31 |
||
|} |
|} |
||
|| Най-малкият елемент |
|| Най-малкият оставащ елемент е 12. Разменят се 12 и 34. |
||
|- |
|- |
||
| |
| |
||
Ред 83: | Ред 60: | ||
| |11||12|| bgcolor="lightblue" |34|| bgcolor="pink" |22||31 |
| |11||12|| bgcolor="lightblue" |34|| bgcolor="pink" |22||31 |
||
|} |
|} |
||
|| Вече имаме една част от списъка, която е сортирана. |
|| Вече имаме една част от списъка, която е сортирана. Сега се разменят 22 и 34. |
||
|- |
|- |
||
| |
| |
||
Ред 89: | Ред 66: | ||
| |11||12||22|| bgcolor="lightblue" |34|| bgcolor="pink" |31 |
| |11||12||22|| bgcolor="lightblue" |34|| bgcolor="pink" |31 |
||
|} |
|} |
||
|| Разменят се |
|| Разменят се 31 и 34. |
||
|- |
|- |
||
| |
| |
||
Ред 98: | Ред 75: | ||
|} |
|} |
||
== Пример на C# за сортиране на |
== Пример на C# за сортиране на числа по метода на прекия избор == |
||
<pre> |
<pre> |
||
using System; |
using System; |
||
Ред 127: | Ред 104: | ||
</pre> |
</pre> |
||
== Пример на C++ за сортиране на |
== Пример на C++ за сортиране на числа по метода на прекия избор == |
||
<code><pre>#include <iostream> |
<code><pre>#include <iostream> |
||
using namespace std; |
using namespace std; |
||
Ред 151: | Ред 128: | ||
}</pre> |
}</pre> |
||
[[Категория:Алгоритми]] |
[[Категория:Алгоритми]] |
Версия от 07:04, 1 август 2017
В компютърните науки методът на пряката селекция (Шаблон:Lang-en) е алгоритъм за сортиране. Той е един от фундаменталните методи за сортиране и е прост и лесен на имплементиране.
Алгоритъмът има сложност от Θ(n2), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за сортиране чрез вмъкване (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.
Принцип на действие
Алгоритъмът работи по следния начин:
- Намира най-малкия елемент в списъка като сравнява първият елемент с всички останали
- Разменя го с елемента на първа позиция
- Повтаря горните две стъпки за всеки следващ елемент
Пример стъпка по стъпка
Нека имаме масив със следните елементи: 64,25,12,22,11 и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни.
Първо преминаване:
64 25 12 22 11 25 64 12 22 11
25 64 12 22 11 12 64 25 22 11
12 64 25 22 11 12 64 25 22 11
12 64 25 22 11 11 64 25 22 12
След първото преминаване най-малкият елемент на масива се намира на първа позиция.
Второ преминаване:
11 64 25 22 12 11 25 64 22 12
11 25 64 22 12 11 22 64 25 12
11 22 64 25 12 11 12 64 25 22
Трето преминаване:
11 12 64 25 22 11 12 25 64 22
11 12 25 64 22 11 12 22 64 25
Четвърто преминаване:
11 12 22 64 25 11 12 22 25 64
Анализ
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми. За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи (това отнема n – 1 сравнения) и след това да го разменим с първата позиция. За да намерим следващият най-малък елемент се изисква да сканираме оставащите n – 1 елементи и така нататък. Общият брой сравнения е равен на
(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 = Θ(n2)
според формулата за сбор на аритметична прогресия. Всяко от тези n – 1 преминавания по масива изисква една размяна на елементи (последният елемент е вече на правилното място).
Сравнение с други алгоритми за сортиране
Методът на прекия избор почти винаги е по-бърз от метода на мехурчето и метода на гнома. Сортирането чрез вмъкване и чрез пряка селекция си приличат по това, че след k-тата итерация първите k елемента на масива са подредени във възходящ ред. Предимството на метода на вмъкването е, че проверява толкова елемента, колкото му е нужно, за да сложи (k + 1)-ия елемент на мястото му, докато методът на пряката селекция трябва да провери всички останали елементи, за да намери (k + 1)-ия елемент.
Сортирането чрез вмъкване прави средно два пъти по-малко сравнения от метода на прекия избор. Недостатък на последния метод е, че работи едно и също време независимо от подредбата на входния масив, дори когато той е предварително сортиран. Сортирането чрез вмъкване е по-адаптивно: то работи бързо, когато масивът е сортиран или почти сортиран.
Върху големи масиви методът на пряката селекция е доста по-бавен от сортирането чрез сливане и други бързи сортировки. Обаче сортирането чрез пряк избор и чрез вмъкване са по-бързи, когато работят върху малки масиви (до десет-двайсет елемента). Затова тези два метода се използват като дъно на някои рекурсивни сортировки, например бързото сортиране (quick sort).
Варианти
Пирамидалното сортиране (heap sort) значително ускорява метода на пряката селекция с помощта на специална структура от данни, наречена пирамида (heap). Тя позволява намирането и изтриването на следващия най-малък елемент с Θ(log n) стъпки вместо Θ(n).
Двупосочен вариант на метода на пряката селекция, наричан още метод на коктейла (cocktail sort), е алгоритъм, който при всяко преминаване през масива намира едновременно най-малкия и най-големия от останалите елементи. Това намалява броя на преминаванията, но не и броя на сравненията и размените.
Понякога методът на коктейла се смята за двупосочен вариант на метода на мехурчето.
Сортирането чрез пряк избор е устойчива сортировка: при внимателно реализиране то не разменя елементи с равни ключове.
Пример
|
Най-малкият елемент е 11. Разменят се 11 и 31. | |||||
|
Най-малкият оставащ елемент е 12. Разменят се 12 и 34. | |||||
|
Вече имаме една част от списъка, която е сортирана. Сега се разменят 22 и 34. | |||||
|
Разменят се 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;
}