Сортиране чрез пряка селекция: Разлика между версии
Облик
Изтрито е съдържание Добавено е съдържание
м Робот Добавяне: sr:Сортирање селекцијом |
SilvonenBot (беседа | приноси) м Робот Добавяне: sv:Urvalssortering |
||
Ред 88: | Ред 88: | ||
[[ru:Сортировка выбором]] |
[[ru:Сортировка выбором]] |
||
[[sr:Сортирање селекцијом]] |
[[sr:Сортирање селекцијом]] |
||
[[sv:Urvalssortering]] |
|||
[[tr:Seçmeli sıralama]] |
[[tr:Seçmeli sıralama]] |
||
[[uk:Сортування вибором]] |
[[uk:Сортування вибором]] |
Версия от 16:03, 7 март 2009
Сортирането чрез пряка селекция (метод на пряката селекция, Шаблон: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(i=0; i<5; i++)
cout << array[i] << "\t";
return 0;
}