This content originally appeared on DEV Community and was authored by
(Първо публикувано на 16.01.2017)
Е, стигнах и до разглеждането на някои “brute force” алгоритми! 
Какво представляват тези алгоритми? Общо взето при тях просто пробваме всички възможни решения докато не стигнем до такова, което… ами… работи. Например ако играем шах, brute force подходът за победа би бил да пробваме *всяка *комбинация от ходове докато не спечелим, без да обръщаме внимание на подредбата на фигурите (да, дори пешката в началото, която няма шанс да стигне до царя, ще бъде преместена). Това, разбира се, би отнело прекалено много ресурси и време, но показва как точно работи един brute force алгоритъм.
Сортирането чрез селекция (или “Selection Sort”) е отличен пример за такъв вид алгоритъм и си струва да го знаете.
Преди да започна да пиша по темата, мога да ви спестя доста време и просто да ви дам линк към един феноменален сайт, в който много добре са обяснени всякакви алгоритми за сортиране: Selection Sort @ AlgoList. Имплементациите им са най-разбираемите, които съм срещал!
Както и да е, нека и аз да се опитам да ви представя как работи Selection Sort! Това е може би най-простият алгоритъм за сортиране (първоначално мислех, че е Bubble Sort, но ще стигнем и до него 
).
ОПИСАНИЕ:
“Selection Sort” е алгоритъм за сортиране (т.е. подреждане на елементи във възходящ или низходящ ред) и, както казахме, е добър пример за brute force алгоритъм. Това е така, защото се преглежда целият входен списък и от него се избира минимален елемент.
Този алгоритъм е подходящ за малки списъци, тъй като за по-големи ще е прекалено бавен (за такива списъци съществуват други по-ефективни алгоритми като Quick Sort).
Може да се каже, че това е “инстинктивният” начин, по който бихме сортирали един списък (ако нямаме понятие за други съществуващи алгоритми).
Сложността на алгоритъма е O(n²).
АЛГОРИТЪМ:
- Разделяме списъка/масива на 2 части — сортирана и несортирана.
В началото сортираната част е празна, а несортираната включва целия масив.
- На всяка стъпка намираме минималния елемент в несортираната част.
Добавяме го в края на сортираната част.
- Когато несортираната част стане празна — алгоритъмът приключва.
—
Можем да формулираме алгоритъма и по друг начин, който ни дава по-ясна представа как да го имплементираме (т.е. да го напишем на език за програмиране).
Намираме елемента с най-малката стойност в списъка.
Разменяме стойностите на намерения и 0-ия елемент.
На 0-вото място вече е най-малкият елемент.Повтаряме същата процедура (стъпка 1) с подмасива, започващ от 1-ия елемент.
Поставяме втория по големина елемент на 1-во място (позицията след 0-ия елемент).
Повтаряме същото със следващия подмасив.Накрая повтаряме същата процедура с подмасива, започващ от предпоследния елемент, т.е. за подмасива, състоящ се от предпоследния и последния елемент.
Сортирането завършва.
ПРИМЕР:
Нека сортираме следната последователност от числа:
89, 45, 68, 90, 29, 34, 17
Ще ви обясня по-”сложната” версия на алгоритъма, за да разберете как точно ще работи кодът по-долу.
Първо нека представим тази последователност от числа като масив и отгоре напишем индекса на всеки елемент:
Нека започнем с алгоритъма! Първо трябва да намерим минимания елемент. Бързо виждаме, че това е последният елемент (индекс 6, стойност 17). Нека го маркираме с червен цвят и удебелим 0-вия елемент, с който ще си разменят стойностите (началото на подмасива):
Разменяме стойностите:
Продължаваме по същата процедура, но този път започваме от елемент 1. Сега най-малкият елемент става този с индекс 4 (29):
Разменяме го с елемент 1:
Схванахте идеята… сега започваме от елемент 2 и виждаме, че минималният елемент е този с индекс 5 (34):
Разменяме ги:
Започваме от елемент 3. Минималният след него е елемент 4 (45):
Разменяме ги:
Преминаваме към елемент 4 и сега минималният до него става елемент 5 (68):
Разменяме ги:
Стигнахме до последната итерация! Сега сме на подмасива от предпоследния и последния елемент. Виждаме, че ще трябва да ги разменим:
Разменяме ги:
Сега масивът е сортиран и изглежда така:
Сортираната последователност ще изглежда така:
17, 29, 34, 45, 68, 89, 90
ИМПЛЕМЕНТАЦИЯ (Java):
—
Това е за днес! Ако видите някоя неточност, just whistle. 
This content originally appeared on DEV Community and was authored by