selection sort c with examples
En grundig titt på utvalg Sorter i C ++ med eksempler.
Som navnet antyder, velger sorteringsteknikken for det første det minste elementet i matrisen og bytter det med det første elementet i matrisen.
Deretter bytter det det nest minste elementet i matrisen med det andre elementet og så videre. For hvert pass blir det minste elementet i matrisen valgt og satt i riktig posisjon til hele matrisen er sortert.
=> Sjekk ut den perfekte C ++ treningsguiden her.
Hva du vil lære:
- Introduksjon
- Generell algoritme
- Pseudokode for utvalgssortering
- Illustrasjon
- C ++ Eksempel
- Java-eksempel
- Kompleksitetsanalyse av utvalgssortering
- Konklusjon
- Anbefalt lesing
Introduksjon
Utvalgssortering er ganske grei sorteringsteknikk, da teknikken bare innebærer å finne det minste elementet i hvert pass og plassere det i riktig posisjon.
Valgsortering fungerer effektivt når listen som skal sorteres, er liten, men ytelsen påvirkes dårlig ettersom listen som skal sorteres, blir større.
Derfor kan vi si at utvalgssortering ikke er tilrådelig for større lister med data.
Generell algoritme
Generell algoritme for utvalgssortering er gitt nedenfor:
Python intervju spørsmål og svar for testere
Valgsortering (A, N)
Trinn 1 : Gjenta trinn 2 og 3 for K = 1 til N-1
Steg 2 : Ring rutine minste (A, K, N, POS)
Trinn 3 : Bytt A (K) med A (POS)
(End of loop)
Trinn 4 : EXIT
Rutineminnes minste (A, K, N, POS)
- Trinn 1 : (initialize) set smallestElem = A (K)
- Steg 2 : (initialiser) sett POS = K
- Trinn 3 : for J = K + 1 til N -1, gjenta
hvis minsteElem> A (J)
sett smallestElem = A (J)
sett POS = J
(hvis slutt)
(End of loop) - Trinn 4 : returner POS
Pseudokode for utvalgssortering
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 for å illustrere denne valgsorteringsalgoritmen er vist nedenfor.
Illustrasjon
Tabellframstillingen for denne illustrasjonen er vist nedenfor:
Usortert liste Minst element Sortert 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) {tjue} tjue {2,7,10,18} {} {2,7,10,18,20}
Fra illustrasjonen ser vi at for hvert pass blir det neste minste elementet satt i riktig posisjon i den sorterte matrisen. Fra illustrasjonen ovenfor ser vi at for å kunne sortere en matrise på 5 elementer, var det nødvendig med fire passeringer. Dette betyr generelt at vi for å sortere en rekke N-elementer trenger N-1-passeringer totalt.
Nedenfor er implementeringen av utvalgssorteringsalgoritmen 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< Produksjon:
Inngangsliste over elementer som skal sorteres
11 5 2 20 42 53 23 34 101 22
Sortert liste over elementer er
2 5 11 20 22 23 34 42 53 101
Antall passeringer som kreves for å sortere matrisen: 10
Som vist i programmet ovenfor, begynner vi sorteringen ved å sammenligne det første elementet i matrisen med alle de andre elementene i matrisen. På slutten av denne sammenligningen plasseres det minste elementet i matrisen i første posisjon.
I neste pass, ved å bruke samme tilnærming, blir det neste minste elementet i matrisen plassert i riktig posisjon. Dette fortsetter til N-elementer, eller til hele matrisen er sortert.
Java-eksempel
Deretter implementerer vi utvalgssorteringsteknikken på Java-språket.
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) Produksjon:
Inngangsliste som skal sorteres ...
11 5 2 20 42 53 23 34 101 22
skriver ut sorterte elementer ...
2 5 11 20 22 23 34 42 53 101
I det ovennevnte java-eksemplet bruker vi også den samme logikken. Vi finner gjentatte ganger det minste elementet i matrisen og legger det i den sorterte matrisen til hele matrisen er fullstendig sortert.
Dermed er utvalgssortering den enkleste algoritmen å implementere, ettersom vi bare må gjentatte ganger finne det neste minste elementet i matrisen og bytte den med elementet i riktig posisjon.
Kompleksitetsanalyse av utvalgssortering
Som det fremgår av pseudokoden ovenfor for utvalgssortering, vet vi at valgsortering krever to for løkker nestet med hverandre for å fullføre seg selv. En for loop går gjennom alle elementene i matrisen, og vi finner minimumselementindeksen ved å bruke en annen for loop som er nestet inne i den ytre for loop.
Derfor, gitt en størrelse N på inngangsmatrisen, har valgsorteringsalgoritmen følgende tids- og kompleksitetsverdier.
Kompleksitet i verste fall O (n 2); O (n) bytter Kompleksitet i beste fall O (n 2); O (n) bytter Gjennomsnittlig tidskompleksitet O (n 2); O (n) bytter Romkompleksitet O (1)
Tidskompleksiteten til O ( n to) er hovedsakelig på grunn av bruken av to til løkker. Merk at valgsorteringsteknikken aldri tar mer enn O (n) -bytter og er gunstig når minneskrivoperasjonen viser seg å være kostbar.
Konklusjon
Selection sort er nok en enkleste sorteringsteknikk som enkelt kan implementeres. Valgsortering fungerer best når rekkevidden til verdiene som skal sorteres er kjent. Således når det gjelder sortering av datastrukturer ved bruk av utvalgssortering, kan vi bare sortere datastrukturen som er lineær og av endelig størrelse.
Dette betyr at vi effektivt kan sortere datastrukturer som matriser ved hjelp av valgsorteringen.
I denne veiledningen har vi diskutert utvalgssortering i detalj, inkludert implementering av utvalgssortering ved hjelp av C ++ og Java-språk. Logikken bak utvalgssorteringen er å finne det minste elementet i listen gjentatte ganger og plassere det i riktig posisjon.
I neste opplæring vil vi lære i detalj om innsettingssortering som sies å være en mer effektiv teknikk enn de to andre teknikkene vi har diskutert så langt, dvs. sortering av boble og utvalg.
=> Sjekk her for å se AZ av C ++ opplæringsveiledninger her.
Anbefalt lesing
- Skalsortering i C ++ med eksempler
- MongoDB Sort () Metode med eksempler
- Unix sorteringskommando med syntaks, alternativer og eksempler
- Boblesortering i C ++ med eksempler
- Innsettingssortering i C ++ med eksempler
- Flett sortering i C ++ med eksempler
- Haugsortering i C ++ med eksempler
- Rask sortering i C ++ med eksempler
