selection sort c with examples
En djupgående titt på urvalet Sortera i C ++ med exempel.
Som själva namnet antyder väljer urvalssorteringstekniken först det minsta elementet i matrisen och byter det med det första elementet i matrisen.
Därefter byter det det näst minsta elementet i matrisen med det andra elementet och så vidare. Således väljs det minsta elementet i matrisen för varje pass och placeras i rätt läge tills hela matrisen sorteras.
=> Kolla in den perfekta C ++ träningsguiden här.
Vad du kommer att lära dig:
- Introduktion
- Allmän algoritm
- Pseudokod för urvalssortering
- Illustration
- C ++ Exempel
- Java-exempel
- Komplexitetsanalys av urvalssortering
- Slutsats
- Rekommenderad läsning
Introduktion
Selektionssortering är en ganska enkel sorteringsteknik eftersom tekniken bara innebär att hitta det minsta elementet i varje pass och placera det i rätt position.
Urvalsortering fungerar effektivt när listan som ska sorteras är liten men dess prestanda påverkas dåligt eftersom listan som ska sorteras växer i storlek.
Därför kan vi säga att val av sortering inte är tillrådligt för större datalistor.
Allmän algoritm
Den allmänna algoritmen för urvalsortering ges nedan:
det stöder frågor och svar på teknikerintervjuer
Urvalssortering (A, N)
Steg 1 : Upprepa steg 2 och 3 för K = 1 till N-1
Steg 2 : Samtalsrutin minsta (A, K, N, POS)
Steg 3 : Byt A [K] med A [POS]
[Slut på slingan]
Steg 4 : UTGÅNG
Rutinmässig minsta (A, K, N, POS)
- Steg 1 : [initialisera] set smallestElem = A [K]
- Steg 2 : [initialisera] ställa in POS = K
- Steg 3 : för J = K + 1 till N -1, upprepa
om minstaElem> A [J]
set smallestElem = A [J]
ställ in POS = J
[om slutet]
[Slut på slingan] - Steg 4 : returnera POS
Pseudokod för urvalssortering
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] Ett exempel för att illustrera denna urvalssorteringsalgoritm visas nedan.
Illustration
Tabellföreställningen för denna illustration visas nedan:
Osorterad lista Minsta element Sorterad lista {18,10,7,20,2} två {} {18,10,7,20} 7 {två} {18,10,20} 10 {2.7} {18.20} 18 {2,7,10) {tjugo} tjugo {2,7,10,18} {} {2,7,10,18,20}
Från illustrationen ser vi att nästa minsta element placeras i rätt position i den sorterade matrisen med varje pass. Från ovanstående illustration ser vi att för att sortera en matris med 5 element krävdes fyra pass. Detta innebär i allmänhet, för att sortera en uppsättning N-element, behöver vi totalt N-1-pass.
Nedan följer implementeringen av sorteringsalgoritmen i C ++.
C ++ Exempel
#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:
Inmatningslista över element som ska sorteras
11 5 2 20 42 53 23 34 101 22
Sorterad lista med element är
2 5 11 20 22 23 34 42 53101
Antal pass som krävs för att sortera matrisen: 10
Som visas i ovanstående program börjar vi valssortering genom att jämföra det första elementet i matrisen med alla andra element i matrisen. I slutet av denna jämförelse placeras det minsta elementet i matrisen i första positionen.
I nästa pass, med samma tillvägagångssätt, placeras nästa minsta element i matrisen i sin rätta position. Detta fortsätter tills N-element, eller tills hela matrisen är sorterad.
Java-exempel
Därefter implementerar vi valssorteringstekniken 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] Produktion:
Ingångslista som ska sorteras ...
11 5 2 20 42 53 23 34 101 22
skriver ut sorterade element ...
2 5 11 20 22 23 34 42 53101
Även i ovanstående java-exempel tillämpar vi samma logik. Vi hittar upprepade gånger det minsta elementet i matrisen och placerar det i den sorterade matrisen tills hela matrisen är helt sorterad.
Således är valssortering den enklaste algoritmen att implementera, eftersom vi bara måste hitta upprepade gånger nästa minsta element i matrisen och byta ut det med elementet på rätt plats.
Komplexitetsanalys av urvalssortering
Som vi ser i pseudokoden ovan för val av sortering, vet vi att urvalssortering kräver två för loopar som är kapslade med varandra för att slutföra sig själv. En för loop går igenom alla element i matrisen och vi hittar minimumelementindexet med en annan för loop som är kapslad inuti det yttre för loop.
Därför, med tanke på en storlek N för inmatningsmatrisen, har valssorteringsalgoritmen följande tids- och komplexitetsvärden.
Värsta fallets tidskomplexitet O (n2); O (n) byter Komplexitet i bästa fall O (n2); O (n) byter Genomsnittlig tidskomplexitet O (n2); O (n) byter Rymdkomplexitet O (1)
Tidskomplexiteten hos O ( n två) beror främst på användningen av två för öglor. Observera att valssorteringstekniken aldrig tar mer än O (n) -byten och är fördelaktig när minnesskrivningen visar sig vara kostsam.
Slutsats
Selection sort är ännu en enklaste sorteringsteknik som enkelt kan implementeras. Valssortering fungerar bäst när intervallet för värdena som ska sorteras är känt. Således när det gäller sortering av datastrukturer med hjälp av urvalsortering kan vi bara sortera datastrukturen som är linjära och av begränsad storlek.
Detta innebär att vi effektivt kan sortera datastrukturer som matriser med hjälp av urvalsorteringen.
I denna handledning har vi diskuterat urvalssortering i detalj inklusive implementering av urvalsortering med C ++ - och Java-språk. Logiken bakom urvalssorteringen är att hitta det minsta elementet i listan upprepade gånger och placera det i rätt position.
I nästa handledning kommer vi att lära oss mer i detalj om insättningssortering som sägs vara en mer effektiv teknik än de andra två teknikerna som vi har diskuterat hittills, dvs. bubblasortering och urvalsortering.
=> Kolla här för att se A-Z av C ++ utbildningstutorialer här.
Rekommenderad läsning
- Skalsortering i C ++ med exempel
- MongoDB Sort () -metod med exempel
- Unix Sorteringskommando med syntax, alternativ och exempel
- Bubblesortering i C ++ med exempel
- Insättningssortering i C ++ med exempel
- Slå ihop sortering i C ++ med exempel
- Heapsortering i C ++ med exempel
- Snabbsortering i C ++ med exempel