Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Luckas-bot (беседа | приноси) м r2.7.1) (Робот Добавяне: hy:Selection sort |
м r2.7.1) (Робот Добавяне: ar:ترتيب إنتقائي |
||
Ред 70: | Ред 70: | ||
[[Категория:Алгоритми]] |
[[Категория:Алгоритми]] |
||
[[ar:ترتيب إنتقائي]] |
|||
[[cs:Selection sort]] |
[[cs:Selection sort]] |
||
[[da:Udtagelsessortering]] |
[[da:Udtagelsessortering]] |
Версия от 13:42, 24 август 2011
Сортирането чрез пряка селекция (метод на пряката селекция, Шаблон:Lang-en) е един от простите алгоритми за сортиране.
Алгоритъмът има сложност от Θ(n2), т.е. времето за изпълнението му е пропорционално на квадрата на броя на елементите в масива. Това го прави неефикасен при големи списъци и като цяло работи по-зле от подобния му алгоритъм за сортиране чрез вмъкване (insertion sort). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.
Принцип на действие
Алгоритъмът работи по следния начин:
- Намира най-малкия елемент в списъка
- Разменя го с елемента на първа позиция
- Повтаря горните две стъпки за остатъка от списъка
Пример
|
Най-малкият елемент е 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;
}