Сортиране чрез пряка селекция: Разлика между версии

от Уикипедия, свободната енциклопедия
Изтрито е съдържание Добавено е съдържание
AvocatoBot (беседа | приноси)
Addbot (беседа | приноси)
м Робот: Преместване на 30 междуезикови препратки към Уикиданни, в d:q220831.
Ред 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). Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.

Принцип на действие

Алгоритъмът работи по следния начин:

  1. Намира най-малкия елемент в списъка
  2. Разменя го с елемента на първа позиция
  3. Повтаря горните две стъпки за остатъка от списъка

Пример

31 34 12 22 11
Най-малкият елемент е 11. Разменят се местата на 11 и 31.
11 34 12 22 31
Най-малкият елемент от останалия списък е 12. Разменят се местата на 12 и 34.
11 12 34 22 31
Вече имаме една част от списъка, която е сортирана. Разменят се местата на 22 и 34.
11 12 22 34 31
Разменят се местата на 31 и 34.
11 12 22 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;

}