Сортиране чрез пряка селекция: Разлика между версии
Shegobieca (беседа | приноси) |
Shegobieca (беседа | приноси) |
||
Ред 30: | Ред 30: | ||
за което ще работи методът на вмъкването може да варира значително. Обаче, в повечето случаи това може да се разглежда като предимство за метода на |
за което ще работи методът на вмъкването може да варира значително. Обаче, в повечето случаи това може да се разглежда като предимство за метода на |
||
вмъкването, защото работи много по-ефикасно, ако масивът е сортиран или "близо до сортиран". |
вмъкването, защото работи много по-ефикасно, ако масивът е сортиран или "близо до сортиран". |
||
Накрая, методът е пряката селекция е доста по-малко производителен върху големи масиви от Θ(n log n) разделяй-и-владей алгоритми като метода на сливане |
|||
(merge sort). Обаче методът на пряката селекция и методът на вмъкване са по-бързи, когато работят върху малки масиви(10 - 20 елемента). Полезна оптимизация |
|||
в практиката за рекурсивните алгоритми е да се смени към метода на вмъкване или метода на пряката селекция, когато елементите от несортирания масив станат |
|||
по-малко от 20. |
|||
== Пример == |
== Пример == |
Версия от 23:57, 18 август 2013
В компютърните науки методът на пряката селекция е алгоритъм за сортиране. Той е един от фундаменталните методи за сортиране и е прост и лесен на имплементиране.
Алгоритъмът има сложност от Θ(n2), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за сортиране чрез вмъкване (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.
Принцип на действие
Алгоритъмът работи по следния начин:
- Намира най-малкия елемент в списъка като сравним първият елемент с всички останали
- Разменя го с елемента на първа позиция
- Повтаря горните две стъпки за всеки следващ елемент
Пример стъпка по стъпка
Нека имаме масив със следните елементи: 64,25,12,22,11и искаме да го сортираме във възходящ ред като използваме метода на пряката селекция. На всяка стъпка елементите, които са удебелени биват разменяни.
64,25,12,22,11 11 25 12 22 64 -> намираме най-малкия елемент и го слагаме на първа позиция
11 25 12 22 64 11 12 25 22 64 започваме от следващия елемент, защото първият е вече сортиран и на второ място идва вторият най-малък елемент
11 12 25 22 64 11 12 22 25 64 започваме от третият елемент и сравняваме с останалата част
11 12 22 25 64 11 12 22 25 64 няма нужда да сравнямаме последният елемент, защото всички останали елементи са вече сортирани и затова последният елемент си е на мястото
Анализ
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми.За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи(това отнеме n - 1 сравнения) и след това да го разменим с първата позиция.За да намерим следващият най-малък елемент се изисква да сканираме оставащите n - 1 елементи и така нататък, за (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) сравнения(виж аритметична прогресия). Всяко от тези сканирания изисква 1 разменяне за n-1 елементи (последният елемент е вече на правилното място)
Сравнение с други алгоритми за сортиране
Спрямо други прости Θ(n2) алгоритми, методът на пряката селекция почти винага е по-бърз от метода на мехурчето и метода на гнома(gnome sort). Методът на вмъкването е много подобен в това, че след k-та итерация, първите k елеметнa в масива са в сортиран ред. Предимството на метода на вмъкването е, че сканира толкова елемента колкото му е нужно за да сложи k + 1 елемент на мястото му, докато методът на пряката селекция трябва да сканира всички останали елементи за да намери k + 1 елемент.
Прости сметки показват, че следователно на метода на вмъкването ще са му нужни 2 пъти по-малко сравнения спрямо метода на пряката селекция. Може да се разглежда като предимство за някои real-time апликации, че методът на пряката селекция ще работи идентично без значение от реда на масива, докато времето, за което ще работи методът на вмъкването може да варира значително. Обаче, в повечето случаи това може да се разглежда като предимство за метода на вмъкването, защото работи много по-ефикасно, ако масивът е сортиран или "близо до сортиран".
Накрая, методът е пряката селекция е доста по-малко производителен върху големи масиви от Θ(n log n) разделяй-и-владей алгоритми като метода на сливане (merge sort). Обаче методът на пряката селекция и методът на вмъкване са по-бързи, когато работят върху малки масиви(10 - 20 елемента). Полезна оптимизация в практиката за рекурсивните алгоритми е да се смени към метода на вмъкване или метода на пряката селекция, когато елементите от несортирания масив станат по-малко от 20.
Пример
|
Най-малкият елемент е 11. Разменят се местата на 11 и 31. | |||||
|
Най-малкият елемент от останалия списък е 12. Разменят се местата на 12 и 34. | |||||
|
Вече имаме една част от списъка, която е сортирана. Разменят се местата на 22 и 34. | |||||
|
Разменят се местата на 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;
}