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

от Уикипедия, свободната енциклопедия
Изтрито е съдържание Добавено е съдържание
MerlIwBot (беседа | приноси)
м Робот Добавяне: tl:Selection sort
AvocatoBot (беседа | приноси)
Ред 94: Ред 94:
[[sr:Сортирање селекцијом]]
[[sr:Сортирање селекцијом]]
[[sv:Urvalssortering]]
[[sv:Urvalssortering]]
[[th:การเรียงลำดับแบบเลือก]]
[[tl:Selection sort]]
[[tl:Selection sort]]
[[tr:Seçmeli sıralama]]
[[tr:Seçmeli sıralama]]

Версия от 19:11, 15 май 2012

Сортирането чрез пряка селекция (метод на пряката селекция, Шаблон: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;

}