Какво представляват тези алгоритми? Общо взето при тях просто пробваме всички възможни решения докато не стигнем до такова, което... ами... работи. Например ако играем шах, brute force подходът за победа би бил да пробваме всяка комбинация от ходове докато не спечелим, без да обръщаме внимание на подредбата на фигурите (да, дори пешката в началото, която няма шанс да стигне до царя, ще бъде преместена). Това, разбира се, би отнело прекалено много ресурси и време, но показва как точно работи един brute force алгоритъм.
Сортирането чрез селекция (или "Selection Sort") е отличен пример за такъв вид алгоритъм и си струва да го знаете.
Преди да започна да пиша по темата, мога да ви спестя доста време и просто да ви дам линк към един феноменален сайт, в който много добре са обяснени всякакви алгоритми за сортиране: Selection Sort @ AlgoList. Имплементациите им са най-разбираемите, които съм срещал!
Както и да е, нека и аз да се опитам да ви представя как работи Selection Sort! Това е може би най-простият алгоритъм за сортиране (първоначално мислех, че е Bubble Sort, но ще стигнем и до него 😮).
---
ОПИСАНИЕ:
"Selection Sort" е алгоритъм за сортиране (т.е. подреждане на елементи във възходящ или низходящ ред) и, както казахме, е добър пример за brute force алгоритъм. Това е така, защото се преглежда целият входен списък и от него се избира минимален елемент.
Този алгоритъм е подходящ за малки списъци, тъй като за по-големи ще е прекалено бавен (за такива списъци съществуват други по-ефективни алгоритми като Quick Sort).
Може да се каже, че това е "инстинктивният" начин, по който бихме сортирали един списък (ако нямаме понятие за други съществуващи алгоритми).
Сложността на алгоритъма е O(n^2).
АЛГОРИТЪМ:
1. Разделяме списъка/масива на 2 части - сортирана и несортирана.
В началото сортираната част е празна, а несортираната включва целия масив.
2. На всяка стъпка намираме минималния елемент в несортираната част.
Добавяме го в края на сортираната част.
3. Когато несортираната част стане празна - алгоритъмът приключва.
---
Можем да формулираме алгоритъма и по друг начин, който ни дава по-ясна представа как да го имплементираме (т.е. да го напишем на език за програмиране).
1. Намираме елемента с най-малката стойност в списъка.
Разменяме стойностите на намерения и 0-ия елемент.
На 0-вото място вече е най-малкият елемент.
2. Повтаряме същата процедура (стъпка 1) с подмасива, започващ от 1-ия елемент.
Поставяме втория по големина елемент на 1-во място (позицията след 0-ия елемент).
Повтаряме същото със следващия подмасив.
3. Накрая повтаряме същата процедура с подмасива, започващ от предпоследния елемент, т.е. за подмасива, състоящ се от предпоследния и последния елемент.
4. Сортирането завършва.
ПРИМЕР:
Нека сортираме следната последователност от числа:
Ще ви обясня по-"сложната" версия на алгоритъма, за да разберете как точно ще работи кодът по-долу.
Първо нека представим тази последователност от числа като масив и отгоре напишем индекса на всеки елемент:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
89
|
45
|
68
|
90
|
29
|
34
|
17
|
---
Нека започнем с алгоритъма! Първо трябва да намерим минимания елемент. Бързо виждаме, че това е последният елемент (индекс 6, стойност 17). Нека го маркираме с червен цвят и удебелим 0-вия елемент, с който ще си разменят стойностите (началото на подмасива):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
89
|
45
|
68
|
90
|
29
|
34
|
17
|
Разменяме стойностите:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
45
|
68
|
90
|
29
|
34
|
89
|
---
Продължаваме по същата процедура, но този път започваме от елемент 1. Сега най-малкият елемент става този с индекс 4 (29):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
45
|
68
|
90
|
29
|
34
|
89
|
Разменяме го с елемент 1:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
68
|
90
|
45
|
34
|
89
|
---
Схванахте идеята... сега започваме от елемент 2 и виждаме, че минималният елемент е този с индекс 5 (34):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
68
|
90
|
45
|
34
|
89
|
Разменяме ги:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
90
|
45
|
68
|
89
|
---
Започваме от елемент 3. Минималният след него е елемент 4 (45):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
90
|
45
|
68
|
89
|
Разменяме ги:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
90
|
68
|
89
|
---
Преминаваме към елемент 4 и сега минималният до него става елемент 5 (68):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
90
|
68
|
89
|
Разменяме ги:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
68
|
90
|
89
|
---
Стигнахме до последната итерация! Сега сме на подмасива от предпоследния и последния елемент. Виждаме, че ще трябва да ги разменим:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
68
|
90
|
89
|
Разменяме ги:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
68
|
89
|
90
|
---
Сега масивът е сортиран и изглежда така:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
Стойност
|
17
|
29
|
34
|
45
|
68
|
89
|
90
|
Сортираната последователност ще изглежда така:
17, 29, 34, 45, 68, 89, 90
ИМПЛЕМЕНТАЦИЯ (Java):
---
Това е за днес! Ако видите някоя неточност, just whistle. 😅
Няма коментари:
Публикуване на коментар