Meni

Izbirno razvrščanje v C ++ z primeri

selection sort c with examples

Preizkusite Naš Instrument Za Odpravo Težav

Poglobljen pogled na izbiro Razvrsti v jeziku C ++ s primeri.

Kot že samo ime pove, tehnika izbire razvrščanja najprej izbere najmanjši element v matriki in ga zamenja s prvim elementom v matriki.

Nato drugi najmanjši element v matriki zamenja z drugim elementom in tako naprej. Tako je za vsak prehod izbran najmanjši element v matriki in postavljen v ustrezen položaj, dokler ni razvrščena celotna matrika.

=> Tukaj si oglejte Perfect Guide za usposabljanje za C ++.

Razvrsti razvrstitev

Kaj se boste naučili:

Uvod

Izbirno razvrščanje je precej enostavna tehnika razvrščanja, saj tehnika vključuje le iskanje najmanjšega elementa v vsakem podajanju in postavitev v pravi položaj.

Izbirno razvrščanje deluje učinkovito, če je seznam, ki ga je treba razvrstiti, majhne velikosti, vendar njegova uspešnost slabo vpliva, saj seznam, ki ga želite razvrstiti, narašča.

Zato lahko rečemo, da izbira ni priporočljiva za večje sezname podatkov.

Splošni algoritem

Splošni algoritem za razvrščanje je podan spodaj:

kako odpreti datoteko jnlp v operacijskem sistemu Windows 10

Razvrstitev izbora (A, N)

Korak 1 : Ponovite 2. in 3. korak za K = 1 do N-1
2. korak : Najmanjša rutina klica (A, K, N, POS)
3. korak : A (K) zamenjajte z A (POS)
(Konec zanke)
4. korak : EXIT

Redno najmanjše (A, K, N, POS)

  • Korak 1 : (inicializiraj) nastavi najmanjšiElem = A (K)
  • 2. korak : (inicializiraj) nastavi POS = K
  • 3. korak : za J = K + 1 do N -1, ponovite
    če je najmanjšiElem> A (J)
    nastavi najmanjšiElem = A (J)
    nastavite POS = J
    (če je konec)
    (Konec zanke)
  • 4. korak : vrnitev POS

Psevkodo za sortiranje izbire

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)

Primer za ponazoritev tega algoritma za razvrščanje je prikazan spodaj.

Ilustracija

Ilustracija sortiranja izbora

Pass2

Pass3

Pass4

Tabelarni prikaz te ilustracije je prikazan spodaj:

Nerazvrščen seznamNajmanj elementRazvrščen seznam
{18,10,7,20,2}dva{}
{18,10,7,20}7.{dva}
{18,10,20}10.{2,7}
{18.20}18.{2,7,10)
{dvajset}dvajset{2,7,10,18}
{}{2,7,10,18,20}

Na sliki vidimo, da je z vsakim prehodom naslednji najmanjši element postavljen v svoj pravilen položaj v razvrščeni matriki. Iz zgornje ilustracije vidimo, da so bili za razvrščanje niza 5 elementov potrebni štirje prehodi. To na splošno pomeni, da za razvrščanje nabora N elementov potrebujemo skupaj N-1 prehodov.

Spodaj je predstavljena izvedba algoritma za razvrščanje v C ++.

Primer 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<

Izhod:

Seznam vnosov elementov, ki jih je treba razvrstiti

11 5 2 20 42 53 23 34 101 22

Razvrščen seznam elementov je

2 5 11 20 22 23 34 42 53 101

Število prehodov, potrebnih za razvrščanje matrike: 10

Kot je prikazano v zgornjem programu, začnemo sortiranje izbire s primerjavo prvega elementa v matriki z vsemi drugimi elementi v matriki. Na koncu te primerjave je najmanjši element v matriki postavljen na prvo mesto.

V naslednjem prehodu se z enakim pristopom naslednji najmanjši element v matriki postavi v svoj pravilen položaj. To se nadaljuje, dokler N elementov ali dokler ni razvrščena celotna matrika.

Primer Java

Nato izvedemo tehniko razvrščanja po izboru v jeziku 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)

Izhod:

Seznam vnosov, ki ga je treba razvrstiti…

11 5 2 20 42 53 23 34 101 22

tiskanje razvrščenih elementov…

2 5 11 20 22 23 34 42 53 101

Tudi v zgornjem primeru Java uporabljamo isto logiko. V matriki večkrat najdemo najmanjši element in ga damo v razvrščeno polje, dokler ni celotno polje popolnoma razvrščeno.

Tako je izbira razvrščanja najpreprostejši algoritem za izvedbo, saj moramo le večkrat najti naslednji najmanjši element v matriki in ga zamenjati z elementom na njegovem ustreznem položaju.

Analiza kompleksnosti sorte izbire

Kot je razvidno iz zgornje psevdokode za izbrano razvrščanje, vemo, da za izbirno razvrščanje potrebujeta dve zanki, ki sta med seboj ugnezdeni. Ena za zanko koraka skozi vse elemente v matriki in najdemo najmanjši indeks elementov z drugo for zanko, ki je ugnezdena znotraj zunanje zanke for.

Zato ima glede na velikost N vhodne matrike algoritem za razvrščanje izbire naslednje vrednosti časa in zahtevnosti.

Najslabša časovna zapletenostO (n2); O (n) zamenjave
Najboljša časovna zapletenostO (n2); O (n) zamenjave
Povprečna časovna zapletenostO (n2); O (n) zamenjave
Zapletenost prostoraO (1)

Časovna zapletenost O ( n dva) je predvsem zaradi uporabe dveh za zanke. Upoštevajte, da tehnika izbire razvrščanja nikoli ne traja več kot zamenjav O (n) in je koristna, če se operacija zapisovanja v pomnilnik izkaže za drago.

Zaključek

Izbirno razvrščanje je še ena najpreprostejša tehnika razvrščanja, ki jo je mogoče enostavno izvajati. Izbirno razvrščanje deluje najbolje, če je znan obseg razvrščenih vrednosti. Kar zadeva razvrščanje podatkovnih struktur z uporabo izbirnega razvrščanja, lahko razvrščamo samo podatkovne strukture, ki so linearne in končne velikosti.

To pomeni, da lahko s pomočjo izbirnega razvrščanja učinkovito razvrstimo podatkovne strukture, kot so nizi.

V tej vadnici smo podrobno razpravljali o razvrščanju izbir, vključno z izvajanjem razvrščanja izbir z uporabo jezikov C ++ in Java. Logika razvrščanja izbire je večkrat najti najmanjši element na seznamu in ga postaviti v pravi položaj.

V naslednji vadnici bomo podrobno izvedeli o razvrščanju vstavljanja, ki naj bi bilo učinkovitejše od ostalih dveh tehnik, o katerih smo razpravljali doslej, tj.

=> Tukaj si oglejte A-Z o vajah za usposabljanje za C ++.

Priporočeno branje

^