Menu

Výber Zoradiť v C ++ s príkladmi

selection sort c with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

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 ++.

Výber Zoradiť

Čo sa dozviete:

Ú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

Výber Zoradiť ilustráciu

Pass2

Pass3

Pass4

Tabuľkové znázornenie tejto ilustrácie je uvedené nižšie:

Netriedený zoznamNajmenej prvokZoradený 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ípaduO (n2); O (n) zámeny
Priemerná časová zložitosťO (n2); O (n) zámeny
Zložitosť priestoruO (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

^