streamalism.org

1. Úvod

V tomto výučbe to urobíme naučiť Selection Sort, pozrite si jeho implementáciu v prostredí Java a analyzujte jeho výkon.

2. Prehľad algoritmov

Výber Zoradiť začína prvkom na 1. pozícii netriedené pole a prehľadá ďalšie prvky do nájsť najmenší prvok. Po nájdení sa najmenší prvok zamení s prvkom na 1. pozícii.

Algoritmus potom prejde k prvku na 2. pozícii a prehľadá nasledujúce prvky, aby našiel index druhého najmenšieho prvku. Po nájdení sa druhý najmenší prvok zamení s prvkom na 2. pozícii.

Tento proces pokračuje, kým sa nedostaneme k n-1. Prvku poľa, čím sa n-1. Najmenší prvok dostane do n-1. Polohy. Posledný prvok automaticky padne na miesto v n-tej iterácii, čím zoradí pole.

Nájdeme najväčší prvok namiesto najmenšieho na zoradenie poľa v zostupnom poradí.

Pozrime sa na príklad netriedeného poľa a zoraďme ho vzostupne, aby sme algoritmu vizuálne porozumeli.

2.1. Príklad

Zvážte nasledujúce netriedené pole:

int [] arr = {5, 4, 1, 6, 2}

Iterácia 1

Vzhľadom na vyššie uvedené fungovanie algoritmu začneme s prvkom na 1. pozícii - 5 - a skenujeme všetky nasledujúce prvky, aby sme našli najmenší prvok - 1. Potom zameníme najmenší prvok s prvkom na 1. pozícii.

Upravené pole teraz vyzerá takto:

{ 1 , 4 , 5 , 6 , 2 }

Celkové vykonané porovnania: 4

Iterácia 2

V druhej iterácii sa presunieme k 2. prvku - 4 - a skenovaním nasledujúcich prvkov nájdeme druhý najmenší prvok - 2. Potom zameníme druhý najmenší prvok s prvkom na 2. pozícii.

Upravené pole teraz vyzerá takto:

{ 1 , 2 , 5 , 6 , 4 }

Celkové vykonané porovnania: 3

Podobne pokračujeme, máme nasledujúce iterácie:

Iterácia 3

{ 1 , 2 , 4 , 6 , 5 }

Celkové vykonané porovnania: 2

Iterácia 4

{ 1 , 2 , 4 , 5 , 6 }

Celkové vykonané porovnania: 1

3.Implementácia

Poďme implementovať Selection Sort pomocou niekoľkých pre slučky:

public static void sortAscending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int minElementIndex = i; pre (int j = i + 1; j arr [j]) {minElementIndex = j; }} if (minElementIndex! = i) {int temp = arr [i]; arr [i] = arr [minElementIndex]; arr [minElementIndex] = teplota; }}}

Samozrejme, aby sme to zvrátili, mohli by sme urobiť niečo celkom podobné:

public static void sortDescending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int maxElementIndex = i; for (int j = i + 1; j <arr.length; j ++) {if (arr [maxElementIndex] <arr [j]) {maxElementIndex = j; }} if (maxElementIndex! = i) {int temp = arr [i]; arr [i] = arr [maxElementIndex]; arr [maxElementIndex] = teplota; }}}

A s trochou väčšieho množstva mazu na lakte by sme ich mohli kombinovať pomocou Komparátors.

4. Prehľad výkonu

4.1. Čas

V príklade, ktorý sme videli skôr, výber najmenšieho prvku vyžadoval celkom (n-1) porovnania nasledovalo jej prehodenie do 1. polohy. Podobne výber nasledujúceho najmenšieho prvku požadovaný súčet (n-2) porovnania, po ktorých nasleduje výmena na 2. pozícii atď.

Počnúc indexom 0 teda vystupujeme n-1, n-2, n-3, n-4…. 1 porovnania. Posledný prvok automaticky zapadne na miesto kvôli predchádzajúcim iteráciám a swapom.

Matematicky súčet prvého n-1 prirodzené čísla nám povie, koľko porovnaní potrebujeme, aby sme zoradili veľkosť poľa n pomocou Selection Sort.

Vzorec pre súčet n prirodzené čísla sú n (n + 1) / 2.

V našom prípade potrebujeme súčet prvých n-1 prirodzené čísla. Preto nahradzujeme n s n-1 vo vyššie uvedenom vzorci získate:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Ako n ^ 2 rastie prominentne ako n rastie, uvažujeme s vyššou silou n ako výkonový štandard, vďaka čomu bude mať tento algoritmus a časová zložitosť O (n ^ 2).

4.2. Vesmír

Z hľadiska zložitosti pomocného priestoru vyžaduje Selection Sort jednu ďalšiu premennú na dočasné zadržanie hodnoty pre zámenu. Preto je výber triedenia zložitosť priestoru je O (1).

5. Záver

Selection Sort je veľmi jednoduchý triediaci algoritmus na pochopenie a implementáciu. Bohužiaľ kvadratická časová zložitosť z neho robí nákladnú techniku ​​triedenia. Pretože algoritmus musí prehľadávať každý prvok, najlepší prípad, priemerný prípad a najhoršia časová zložitosť sú rovnaké.

Ostatné techniky triedenia ako Insertion Sort a Shell Sort majú tiež kvadratickú najhoršiu časovú zložitosť, ale v lepších a priemerných prípadoch fungujú lepšie.

Vyskúšajte kompletný kód Selection Seřadit podľa na GitHub.