Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м Робот Добавяне: nl:Selection sort |
|||
Ред 83: | Ред 83: | ||
[[ko:선택 정렬]] |
[[ko:선택 정렬]] |
||
[[lt:Išrinkimo rikiavimo algoritmas]] |
[[lt:Išrinkimo rikiavimo algoritmas]] |
||
[[nl:Selection sort]] |
|||
[[pl:Sortowanie przez wybieranie]] |
[[pl:Sortowanie przez wybieranie]] |
||
[[pt:Selection sort]] |
[[pt:Selection sort]] |
Версия от 04:22, 25 август 2008
Сортирането чрез пряка селекция (метод на пряката селекция, Шаблон: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;
}