Како се користи сортирање избора

Селекционо сортирање је техника сортирања која бира ставку листе, а затим замењује своје место другом. Бира највећу ставку, а затим је замењује ставком са највишим индексом листе.

Алгоритам то ради више пута док се листа не сортира. Ако нисте сасвим сигурни како сортирање избора функционише, дошли сте на право место. Објаснићемо то детаљније у наставку, заједно са показивањем примера.

Сорта избора: Ближи изглед

Претпоставимо да имате списак: [39, 82, 2, 51, 30, 42, 7]. Да бисте сортирали листу помоћу селекционог сортирања, прво бисте морали пронаћи највећи број у њој.

Уз дати списак, тај број је 82. Замените 82 бројем са највишим индексом (односно 7).

Након првог проласка, нови редослед листе биће: [39, 7, 2, 51, 30, 42, 82]. Сваки пут када алгоритам прође кроз целу листу, то се назива „пролаз“.

Приметите да листа одржава сортирану и несортирану подлисту током процеса сортирања.

Повезан: Шта је Биг-О нотација?

Оригинална листа започиње сортираном листом од нула ставки и неразврстаном листом свих ставки. Затим након првог проласка има сортирану листу која има само број 82.

При другом пролазу, највећи број на несортованој подлистку биће 51. Овај број ће се разменити са 42 да би се добио нови редослед списка у наставку:

[39, 7, 2, 42, 30, 51, 82].

Поступак се понавља док се цела листа не сортира. Доња слика резимира цео процес:

Бројеви подебљани црном бојом показују највећу вредност листе у то време. Они у зеленом приказују сортирану подлистку.

Анализа алгоритма

Да бисте сазнали сложеност (користећи Биг-О нотацију) овог алгоритма, следите доле:

На првом пролазу се праве (н-1) поређења. На другом додавању, (н-2). На трећем пролазу, (н-3) и тако даље до (н-1) тх пролаза који чини само једно поређење.

Резимирање поређења као што следи даје:

(н-1) + (н-1) + (н-1) +... + 1 = ((н-1) н) / 2.

Стога је сортирање избора О (н²).

Имплементација кода

Код приказује функције које можете користити за извршавање сортирања избора помоћу Питхона и Јаве.

Питхон:

деф селецтионСорт (моја листа):
за к у опсегу (лен (милист) - 1, 0, -1):
мак_идк = 0
за посн у опсегу (1, к + 1):
ако је моја листа [посн]> моја листа [мак_идк]:
мак_идк = посн
темп = моја листа [к]
моја листа [к] = моја листа [мак_идк]
милист [мак_идк] = темп

Јава:

воид селецтионСорт (инт ми_арраи []) { 
за (инт к = 0; к { 
инт индекс = к; 
за (инт и = к + 1; и иф (ми_арраи [и] индекс = и; // пронађи најнижи индекс 
} 
} 
инт темп = ми_арраи [индекс]; // темп је привремено складиште
мој_ низ [индекс] = мој_ низ [к]; 
ми_арраи [к] = темп; 
}}

Прелазак са сортирања избора на сортирање стапања

Као што је показала анализа горњег алгоритма, алгоритам сортирања избора је О (н²). Има експоненцијалну сложеност и због тога је неефикасан за веома велике скупове података.

Много бољи алгоритам за коришћење био би спајање сортирања сложености О (нлогн). И сада знате како сортирање избора функционише, следеће на листи студија за алгоритме сортирања треба да буде сортирање спајања.

О аутору