Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Luckas-bot (беседа | приноси) м r2.7.1) (Робот Добавяне: hy:Selection sort |
|||
Ред 80: | Ред 80: | ||
[[fr:Tri par sélection]] |
[[fr:Tri par sélection]] |
||
[[he:מיון בחירה]] |
[[he:מיון בחירה]] |
||
[[hy:Selection sort]] |
|||
[[it:Selection sort]] |
[[it:Selection sort]] |
||
[[ja:選択ソート]] |
[[ja:選択ソート]] |
Версия от 07:04, 15 май 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;
}