selection sort c with examples
Hĺbkový pohľad na výber Zoradenie v C ++ s príkladmi.
Ako už názov napovedá, technika triedenia výberu najskôr vyberie najmenší prvok v poli a zamení ho za prvý prvok v poli.
Ďalej zamení druhý najmenší prvok v poli s druhým prvkom atď. Pri každom prechode sa teda vyberie najmenší prvok v poli a umiestni sa na správne miesto, kým sa celé pole nezoradí.
=> Tu si pozrite perfektného školiaceho sprievodcu pre C ++.
Čo sa dozviete:
- Úvod
- Všeobecný algoritmus
- Pseudokód na výber Zoradiť
- Ilustrácia
- Príklad C ++
- Príklad Java
- Analýza zložitosti výberu
- Záver
- Odporúčané čítanie
Úvod
Výberové triedenie je celkom jednoduchá technika triedenia, pretože táto metóda zahŕňa iba nájdenie najmenšieho prvku v každom prechode a jeho umiestnenie do správnej polohy.
Zoradenie podľa výberu funguje efektívne, keď je zoznam, ktorý chcete triediť, malých rozmerov, ale jeho výkon je zle ovplyvnený, pretože veľkosť zoznamu, ktorý sa má triediť, rastie.
Môžeme teda povedať, že pre väčšie zoznamy údajov nie je vhodné výberové triedenie.
Všeobecný algoritmus
Všeobecný algoritmus pre výberové triedenie je uvedený nižšie:
aký je najlepší firewall zadarmo
Zoradenie podľa výberu (A, N)
Krok 1 : Opakujte kroky 2 a 3 pre K = 1 až N-1
Krok 2 : Volajte najmenšiu rutinu (A, K, N, POS)
Krok 3 : Zamieňajte A (K) s A (POS)
(Koniec slučky)
Krok 4 : VÝCHOD
Rutina najmenšia (A, K, N, POS)
- Krok 1 : (inicializovať) nastaviť najmenšíElem = A (K)
- Krok 2 : (inicializovať) nastaviť POS = K
- Krok 3 : pre J = K + 1 až N -1, opakujte
ak je najmenšíElem> A (J)
nastaviť najmenšíElem = A (J)
nastaviť POS = J
(ak je koniec)
(Koniec slučky) - Krok 4 : spiatočný POS
Pseudokód na výber Zoradiť
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) Nižšie je uvedený príklad na ilustráciu tohto algoritmu triedenia výberu.
Ilustrácia
Tabuľkové znázornenie tejto ilustrácie je uvedené nižšie:
Netriedený zoznam Najmenej prvok Zoradený zoznam {18,10,7,20,2} dva {} {18,10,7,20} 7 {dva} {18,10,20} 10 {2.7} {18.20} 18 {2,7,10) {dvadsať} dvadsať {2,7,10,18} {} {2,7,10,18,20}
Z ilustrácie vidíme, že pri každom prechode sa najbližší najmenší prvok umiestni na správne miesto v zoradenom poli. Z vyššie uvedeného obrázku vidíme, že na roztriedenie poľa 5 prvkov boli potrebné štyri priechody. To znamená, všeobecne, aby sme zoradili pole N prvkov, celkovo potrebujeme N-1 prechodov.
Ďalej je uvedená implementácia algoritmu výberu triedenia v C ++.
Príklad C ++
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<10;i++) { cout< Výkon:
Zadajte zoznam prvkov, ktoré sa majú zoradiť
11 5 2 20 42 53 23 34 101 22
Zoradený zoznam prvkov je
2 5 11 20 22 23 34 42 53 101
Počet prechodov potrebných na zoradenie poľa: 10
Ako je znázornené vo vyššie uvedenom programe, výber začneme výberom porovnania prvého prvku v poli so všetkými ostatnými prvkami v poli. Na konci tohto porovnania je najmenší prvok v poli umiestnený na prvej pozícii.
V ďalšom prechode sa rovnakým prístupom umiestni ďalší najmenší prvok v poli do správnej polohy. Takto to pokračuje až do N prvkov alebo do zoradenia celého poľa.
Príklad Java
Ďalej implementujeme techniku triedenia výberu v jazyku Java.
class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println('
Input list to be sorted...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println('
printing sorted elements...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j) Výkon:
Zoznam vstupov na triedenie ...
11 5 2 20 42 53 23 34 101 22
tlač triedených prvkov ...
2 5 11 20 22 23 34 42 53 101
Aj vo vyššie uvedenom príklade Java používame rovnakú logiku. V poli opakovane nájdeme najmenší prvok a vložíme ho do zoradeného poľa, kým nebude celé pole úplne zoradené.
Výberové triedenie je teda najjednoduchší algoritmus, ktorý je potrebné implementovať, pretože musíme opakovane nájsť ďalší najmenší prvok v poli a zameniť ho s prvkom v príslušnej polohe.
Analýza zložitosti výberu
Ako je vidieť v pseudokode vyššie pre výberové triedenie, vieme, že výberové triedenie vyžaduje dve, aby sa slučky vnorené navzájom dokončili. Jeden pre slučku prechádza všetkými prvkami v poli a minimálny index prvkov nájdeme pomocou iného pre slučku, ktorá je vnorená do vonkajšej slučky for.
Preto vzhľadom na veľkosť N vstupného poľa má algoritmus triedenia výberu nasledujúce hodnoty času a zložitosti.
Najhoršia časová zložitosť O (n2); O (n) zámeny Najlepšia časová zložitosť prípadu O (n2); O (n) zámeny Priemerná časová zložitosť O (n2); O (n) zámeny Zložitosť priestoru O (1)
Časová zložitosť O ( n dva) je to hlavne kvôli použitiu dvoch pre slučky. Pamätajte, že technika triedenia výberu nikdy nezaberie viac ako O (n) swapov a je prospešná, keď sa operácia zápisu do pamäte ukáže ako nákladná.
Záver
Výberové triedenie je ďalšou najjednoduchšou technikou triedenia, ktorú je možné ľahko implementovať. Zoradenie podľa výberu funguje najlepšie, keď je známy rozsah hodnôt, ktoré sa majú zoradiť. Pokiaľ teda ide o triedenie dátových štruktúr pomocou výberového triedenia, môžeme triediť iba dátové štruktúry, ktoré sú lineárne a konečnej veľkosti.
To znamená, že môžeme efektívne triediť dátové štruktúry, ako sú polia, pomocou výberového triedenia.
V tomto tutoriáli sme sa podrobne zaoberali výberovým triedením vrátane implementácie výberového triedenia pomocou jazykov C ++ a Java. Logikou výberu je logické vyhľadanie najmenšieho prvku v zozname opakovane a jeho umiestnenie na správnom mieste.
V ďalšom návode sa podrobne dozvieme o spôsobe vkladania, o ktorom sa hovorí, že je efektívnejšou technikou ako ostatné dve techniky, o ktorých sme doteraz hovorili, a to triedenie podľa bubliniek a výber.
=> Ak chcete vidieť A-Z výučbových kurzov C ++, kliknite sem.
Odporúčané čítanie
- Shell zoradený v C ++ s príkladmi
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Bublinové triedenie v C ++ s príkladmi
- Zoradenie vloženia v C ++ s príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Hromadné triedenie v C ++ s príkladmi
- Rýchle triedenie v C ++ s príkladmi