Сортиране чрез пряка селекция: Разлика между версии
Изтрито е съдържание Добавено е съдържание
AvocatoBot (беседа | приноси) м r2.7.1) (Робот Добавяне: th:การเรียงลำดับแบบเลือก |
|||
Ред 69: | Ред 69: | ||
[[Категория:Алгоритми]] |
[[Категория:Алгоритми]] |
||
[[ar:ترتيب انتقائي]] |
|||
[[cs:Selection sort]] |
|||
[[da:Udtagelsessortering]] |
|||
[[de:Selectionsort]] |
|||
[[en:Selection sort]] |
|||
[[es:Ordenamiento por selección]] |
|||
[[et:Valiksortimine]] |
|||
[[fa:مرتبسازی انتخابی]] |
|||
[[fi:Valintalajittelu]] |
|||
[[fr:Tri par sélection]] |
|||
[[he:מיון בחירה]] |
|||
[[hy:Ընտրության տեսակավորում]] |
|||
[[it:Selection sort]] |
|||
[[ja:選択ソート]] |
|||
[[ko:선택 정렬]] |
|||
[[lt:Išrinkimo rikiavimo algoritmas]] |
|||
[[ml:സെലക്ഷൻ സോർട്ട്]] |
|||
[[nl:Selection sort]] |
|||
[[pl:Sortowanie przez wybieranie]] |
|||
[[pt:Selection sort]] |
|||
[[ru:Сортировка выбором]] |
|||
[[sl:Urejanje z navadnim izbiranjem]] |
|||
[[sr:Сортирање селекцијом]] |
|||
[[sv:Urvalssortering]] |
|||
[[th:การเรียงลำดับแบบเลือก]] |
|||
[[tl:Selection sort]] |
|||
[[tr:Seçmeli sıralama]] |
|||
[[uk:Сортування вибором]] |
|||
[[vi:Sắp xếp chọn]] |
|||
[[zh:选择排序]] |
Версия от 11:53, 15 март 2013
Сортирането чрез пряка селекция (метод на пряката селекция, Шаблон: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;
}