Сортиране чрез пряка селекция: Разлика между версии
Shegobieca (беседа | приноси) Редакция без резюме |
Shegobieca (беседа | приноси) Редакция без резюме |
||
Ред 1: | Ред 1: | ||
В компютърните науки '''методът на пряката селекция''' е алгоритъм за сортиране. Неговата сложност е O(n2), което го прави неефективен за големи колекции и |
|||
'''Сортирането чрез пряка селекция''' (метод на пряката селекция, {{lang-en|selection sort}}) е един от простите [[алгоритми за сортиране]]. |
|||
обикновено работи по-лошо отколкото подобния алгоритъм на вмъкване(insertion sort). Методът на пряката селекция е прост и лесен на имплементиране. |
|||
В някои случаи,най-вече когато допълнителната памет е ограничена има предимство в производителността спрямо по-сложни алгоритми |
|||
Алгоритъмът има [[изчислителна сложност|сложност]] от Θ(''n''<sup>2</sup>), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за [[сортиране чрез вмъкване]] (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни [[алгоритъм|алгоритми]]. |
Алгоритъмът има [[изчислителна сложност|сложност]] от Θ(''n''<sup>2</sup>), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за [[сортиране чрез вмъкване]] (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни [[алгоритъм|алгоритми]]. |
Версия от 23:39, 18 август 2013
В компютърните науки методът на пряката селекция е алгоритъм за сортиране. Неговата сложност е O(n2), което го прави неефективен за големи колекции и обикновено работи по-лошо отколкото подобния алгоритъм на вмъкване(insertion sort). Методът на пряката селекция е прост и лесен на имплементиране. В някои случаи,най-вече когато допълнителната памет е ограничена има предимство в производителността спрямо по-сложни алгоритми
Алгоритъмът има сложност от Θ(n2), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за сортиране чрез вмъкване (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.
Принцип на действие
Алгоритъмът работи по следния начин:
- Намира най-малкия елемент в списъка
- Разменя го с елемента на първа позиция
- Повтаря горните две стъпки за остатъка от списъка
Анализ
Методът на пряката селекция не е труден да се анализира в сравнение с други сортиращи алгоритми.За да намерим най-малкият елемент се изисква да сканираме всички n на брой елементи(това отнеме n - 1 сравнения) и след това да го разменим с първата позиция.За да намерим следващият най-малък елемент се изисква да сканираме оставащите n - 1 елементи и така нататък, за (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) сравнения(виж аритметична прогресия). Всяко от тези сканирания изисква 1 разменяне за n-1 елементи (последният елемент е вече на правилното място)
Пример
|
Най-малкият елемент е 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;
}