selection sort java selection sort algorithm examples
Denne opplæringen vil forklare alt om utvalgssortering i Java sammen med valgsorteringsalgoritme, Java-kode, implementering i Java og Java-eksempler:
Utvalgssorteringsteknikken er en metode der det minste elementet i matrisen er valgt og byttet ut med det første elementet i matrisen. Deretter byttes det nest minste elementet i matrisen med det andre elementet og omvendt.
=> Sjekk her for å se AZ av Java-opplæringsveiledninger her.
Hva du vil lære:
Valgsortering i Java
På denne måten blir det minste elementet i matrisen valgt gjentatte ganger og settes i riktig posisjon til hele matrisen er sortert.
To underordninger opprettholdes for valg av sortering:
- Sortert underrute: I hver iterasjon blir minimumselementet funnet og plassert i riktig posisjon. Denne undergruppen er sortert.
- Usortert undergruppe: De gjenværende elementene som ikke er sortert.
Utvalgssorteringen er en enkel og enkel sorteringsteknikk. Teknikken innebærer bare å finne det minste elementet i hvert pass og plassere det i riktig posisjon. Valgsorteringen er ideell for mindre datasett da den sorterer det mindre datasettet effektivt.
Dermed kan vi si at valgsortering ikke er tilrådelig for større lister med data.
Utvalg Sorteringsalgoritme
Den generelle algoritmen for utvalgssortering er gitt nedenfor:
Valgsortering (A, N)
Trinn 1 : Gjenta trinn 2 og 3 for K = 1 til N-1
Steg 2 : Anropsrutinen minste (A, K, N, POS)
Trinn 3 :
Bytt A [K] med A [POS]
[End of loop]
Trinn 4 : EXIT
Rutinemessig minste (A, K, N, POS)
Trinn 1 : [initialize] set smallestItem = A [K]
Steg 2 : [initialiser] sett POS = K
Trinn 3 :
for J = K + 1 til N -1, gjenta
hvis minsteItem> A [J]
sett smallestItem = A [J]
sett POS = J
[hvis slutt]
[End of loop]
Trinn 4 : returner POS
Som du kan se, blir rutinen for å finne det minste nummeret kalt mens du krysser datasettet. Når det minste elementet er funnet, plasseres det i ønsket posisjon.
virtual reality headset for xbox one
Pseudokode for utvalgssortering
Pseudokoden for valgsorteringsalgoritmen er gitt nedenfor.
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] La oss nå illustrere sorteringen av en matrise ved hjelp av utvalgssortering.
Valgsorteringseksempel
Tenk på følgende matrise som skal sorteres som et eksempel på en utvalgssortering.
Nedenfor er en tabell fremstilling for illustrasjonen:
Usortert liste Minst element Sortert liste {17,10,7,29,2} to {} {17,10,7,29} 7 {to} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
Fra illustrasjonen ser vi at det neste minste elementet blir satt i riktig posisjon i den sorterte matrisen med hvert pass. Generelt, for å sortere en rekke N-elementer, trenger vi totalt N-1-passeringer.
Selection Sort Implementation In Java
La oss nå demonstrere Java-programmet for å implementere utvalgssortering.
import java.util.*; class Main { static void sel_sort(int numArray[]) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Produksjon:
Original Array: [7, 5, 2, 20, 42, 15, 23, 34, 10]
Sortert matrise: [2, 5, 7, 10, 15, 20, 23, 34, 42]
I det ovennevnte java-eksemplet finner vi gjentatte ganger det minste elementet i matrisen og legger det i den sorterte matrisen til hele matrisen er fullstendig sortert.
Valg Sorter koblet liste i Java
Nedenfor er en lenket liste, og vi må sortere den ved hjelp av utvalgssortering. For å gjøre dette vil vi bruke den rekursive tilnærmingen til utvalgssortering. I stedet for å bytte datadelen til noden, vil vi bytte nodene og justere pekerne.
Så hvis den koblede listen er gitt som følger:
Nedenfor er Java-programmet som implementerer sorteringen ovenfor.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data Produksjon:
Opprinnelig koblet liste:
7 9 3 5 1 11
Koblet liste etter sortering:
1 3 5 7 9 11
hvordan man skriver junit test tilfeller i java
Vær oppmerksom på at i det ovennevnte programmet har vi omstilt lenker til nodene i stedet for å sortere bare datakomponenten til noden.
ofte stilte spørsmål
Q # 1) Hvordan fungerer Selection sort?
Svar: Valgsortering fungerer ved å opprettholde to underarrayer. Minimumselementet fra den usorterte undergruppen plasseres i riktig posisjon i en sortert undergruppe. Deretter plasseres det nest laveste elementet i riktig posisjon. På denne måten sorteres hele matrisen ved å velge et minimumselement under hver iterasjon.
Q # 2) Hva er kompleksiteten til utvalgssorteringen?
Svar: Den samlede kompleksiteten til utvalgssorteringen er O (nto), og gjør det dermed til algoritmen som er ineffektiv på større datasett. Andre sorteringsteknikker er mer effektive.
Q # 3) Hva er fordelene og ulempene ved valg?
Svar: Valgsortering er den stedlige sorteringsteknikken, og det krever derfor ikke ekstra lagring for å lagre mellomelementer.
Det fungerer effektivt på mindre datastrukturer, så vel som datasettene som nesten er sortert.
Den største ulempen med utvalgssorteringsteknikken er at den fungerer veldig dårlig når størrelsen på datastrukturen øker. Det blir ikke bare tregere, men reduserer også effektiviteten.
Q # 4) Hvor mange bytter er det i utvalgssorteringen?
Svar: Valgsorteringsteknikken tar minimum antall bytter. For det beste tilfellet, når matrisen er sortert, er antallet bytter i utvalgssorteringen 0.
Q # 5) Er valg sortert raskere enn sortering?
Svar: Innsettingssortering er raskere og mer effektiv og stabil. Valgsortering er raskere bare for mindre datasett og delvis sorterte strukturer.
Konklusjon
Valgsortering er en teknikk som fungerer ved å velge minimumselementet mens du krysser matrisen. For hvert pass / iterasjon velges neste minimumselement i datasettet og plasseres i riktig posisjon.
Utvalgssorteringsteknikken fungerer effektivt når antall elementer i datasettet er mindre, men det begynner å fungere dårlig når størrelsen på datasettet vokser. Det blir ineffektivt sammenlignet med andre lignende teknikker som innsettingssortering.
I denne opplæringen har vi implementert eksempler for å sortere matriser og koblede lister ved hjelp av utvalgssortering.
=> Besøk her for å se Java Training Series for alle.
Anbefalt lesing
- Hvordan sortere en matrise i Java - Veiledning med eksempler
- Valgsortering i C ++ med eksempler
- Java Array Length Tutorial With Code Eksempler
- MongoDB Sort () Metode med eksempler
- Jagged Array In Java - Opplæring med eksempler
- Unix sorteringskommando med syntaks, alternativer og eksempler
- Omvend en matrise i Java - 3 metoder med eksempler
- JAVA-opplæring for nybegynnere: 100+ praktiske Java-videoveiledninger