Menu

Valg af sortering i C ++ med eksempler

selection sort c with examples

Prøv Vores Instrument Til At Fjerne Problemer

Et dybtgående kig på udvælgelsessortering i C ++ med eksempler.

Som selve navnet antyder, vælger sorteringsteknikken for det første det mindste element i arrayet og bytter det med det første element i arrayet.

Derefter bytter det det andet mindste element i arrayet med det andet element og så videre. Således vælges det mindste element i arrayet for hver pasning og placeres i sin rette position, indtil hele arrayet er sorteret.

=> Tjek den perfekte C ++ træningsvejledning her.

Valg Sort

Hvad du lærer:

Introduktion

Selektionssortering er ret ligetil sorteringsteknik, da teknikken kun indebærer at finde det mindste element i hver pasning og placere det i den rigtige position.

Valgssortering fungerer effektivt, når listen, der skal sorteres, er af lille størrelse, men dens ydeevne påvirkes dårligt, da listen, der skal sorteres, vokser i størrelse.

Derfor kan vi sige, at valg af sortering ikke er tilrådeligt for større lister med data.

Generel algoritme

Den generelle algoritme til valg af sortering er angivet nedenfor:

gratis databasesoftware til Windows 10

Valgssortering (A, N)

Trin 1 : Gentag trin 2 og 3 for K = 1 til N-1
Trin 2 : Opkaldsrutine mindste (A, K, N, POS)
Trin 3 : Byt A (K) med A (POS)
(Slut på løkke)
Trin 4 : AFSLUT

Rutinemindste (A, K, N, POS)

  • Trin 1 : (initialize) set smallestElem = A (K)
  • Trin 2 : (initialiser) indstil POS = K
  • Trin 3 : for J = K + 1 til N -1, gentag
    hvis mindsteElem> A (J)
    sæt smallestElem = A (J)
    indstil POS = J
    (hvis slut)
    (Slut på løkke)
  • Trin 4 : returner POS

Pseudokode til valg af sortering

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)

Et eksempel til illustrering af denne valgsorteringsalgoritme er vist nedenfor.

Illustration

Valg Sorter illustration

Pass2

Pass3

Pass4

Tabellerne til denne illustration er vist nedenfor:

Usorteret listeMindste elementSorteret liste
{18,10,7,20,2}to{}
{18,10,7,20}7{to}
{18,10,20}10{2.7}
{18.20}18{2,7,10)
{tyve}tyve{2,7,10,18}
{}{2,7,10,18,20}

Fra illustrationen ser vi, at det næste mindste element med hver pasning placeres i sin korrekte position i det sorterede array. Fra ovenstående illustration ser vi, at for at kunne sortere en matrix på 5 elementer, var der behov for fire gennemløb. Dette betyder generelt, at vi har brug for N-1-passeringer i alt for at sortere en matrix af N-elementer.

Nedenfor er implementeringen af ​​valgsorteringsalgoritme i C ++.

C ++ Eksempel

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

Produktion:

Inputliste over elementer, der skal sorteres

11 5 2 20 42 53 23 34 101 22

Sorteret liste over elementer er

2 5 11 20 22 23 34 42 53101

Antal krævede passeringer for at sortere arrayet: 10

Som vist i ovenstående program begynder vi valgsortering ved at sammenligne det første element i arrayet med alle de andre elementer i arrayet. I slutningen af ​​denne sammenligning placeres det mindste element i arrayet i den første position.

I det næste pass, ved hjælp af samme tilgang, placeres det næste mindste element i arrayet i sin korrekte position. Dette fortsætter indtil N-elementer, eller indtil hele arrayet er sorteret.

Java-eksempel

Dernæst implementerer vi valgsorteringsteknikken på Java-sproget.

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)

Produktion:

Inputliste, der skal sorteres ...

11 5 2 20 42 53 23 34 101 22

udskriver sorterede elementer ...

2 5 11 20 22 23 34 42 53101

Også i ovenstående java-eksempel anvender vi den samme logik. Vi finder gentagne gange det mindste element i arrayet og placerer det i det sorterede array, indtil hele arrayet er helt sorteret.

Således er valgsort den enkleste algoritme at implementere, da vi bare gentagne gange skal finde det næste mindste element i arrayet og bytte det med elementet i den rette position.

Kompleksitetsanalyse af valgsortering

Som det ses i pseudokoden ovenfor for valg af sortering, ved vi, at valg af sortering kræver to for løkker, der er indlejret med hinanden for at fuldføre sig selv. En for loop går gennem alle elementerne i arrayet, og vi finder minimumselementindekset ved hjælp af et andet for loop, der er indlejret inde i det ydre for loop.

Derfor får valgsorteringsalgoritmen, givet en størrelse N af inputmatrixen, følgende tids- og kompleksitetsværdier.

Værst tilfælde tidskompleksitetO (n2); O (n) bytter
Kompleksitet i bedste tilfældeO (n2); O (n) bytter
Gennemsnitlig tidskompleksitetO (n2); O (n) bytter
RumkompleksitetO (1)

Tidskompleksiteten af ​​O ( n to) skyldes hovedsageligt brugen af ​​to til sløjfer. Bemærk, at valgsorteringsteknikken aldrig tager mere end O (n) swaps og er gavnlig, når hukommelsesskrivningsfunktionen viser sig at være dyr.

Konklusion

Selection sort er endnu en enkleste sorteringsteknik, der let kan implementeres. Valgssortering fungerer bedst, når området for de værdier, der skal sorteres, er kendt. Således hvad angår sortering af datastrukturer ved hjælp af udvælgelsessortering, kan vi kun sortere datastruktur, som er lineær og af begrænset størrelse.

Dette betyder, at vi effektivt kan sortere datastrukturer som arrays ved hjælp af valgsorteringen.

I denne vejledning har vi diskuteret valgsortering detaljeret inklusive implementering af valgsortering ved hjælp af C ++ og Java-sprog. Logikken bag markeringen er at finde det mindste element på listen gentagne gange og placere det i den rette position.

I den næste tutorial lærer vi detaljeret om indsættelsessortering, der siges at være en mere effektiv teknik end de to andre teknikker, som vi hidtil har diskuteret, dvs. boblesortering og udvælgelsessortering.

=> Tjek her for at se AZ af C ++ træningsvejledninger her.

Anbefalet læsning

^