Meny

Selection Sort In Java - Selection Sort Algorithm & Exempel

  • Huvud
  • Övrig
  • Selection Sort In Java - Selection Sort Algorithm & Exempel

selection sort java selection sort algorithm examples

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning kommer att förklara allt om urvalssortering i Java tillsammans med urvalssorteringsalgoritm, Java-kod, implementering i Java och Java-exempel:

Valssorteringstekniken är en metod där det minsta elementet i matrisen väljs och byts ut med det första elementet i matrisen. Därefter byts det näst minsta elementet i matrisen ut med det andra elementet och vice versa.

=> Kolla här för att se A-Z av Java-utbildningar här.

Urvalssortering i Java

Vad du kommer att lära dig:

Urvalssortering i Java

På det sättet väljs det minsta elementet i matrisen upprepade gånger och placeras i rätt läge tills hela matrisen sorteras.

Två undergrupper upprätthålls för urvalssortering:

  1. Sorterad undergrupp: I varje iteration finns minimumelementet och placeras i rätt läge. Denna undergrupp är sorterad.
  2. Osorterad undergrupp: De återstående elementen som inte sorteras.

Urvalsorteringen är en enkel och enkel sorteringsteknik. Tekniken innebär bara att hitta det minsta elementet i varje pass och placera det i rätt position. Urvalsorteringen är idealisk för mindre datamängder eftersom den sorterar den mindre datamängden effektivt.

Således kan vi säga att urvalssortering inte är tillrådligt för större datalistor.

Val Sorteringsalgoritm

Den allmänna algoritmen för urvalssortering ges nedan:

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

Rutin minsta (A, K, N, POS)

Steg 1 : (initialisera) ställa in smallestItem = A (K)

Steg 2 : (initialisera) ställa in POS = K

Steg 3 :

för J = K + 1 till N -1, upprepa
om minsta artikel> A (J)
ställa in smallestItem = A (J)
ställ in POS = J
(om slutet)
(Slut på slingan)

Steg 4 : returnera POS

Som du kan se kallas rutinen för att hitta det minsta numret när du går igenom datamängden. När det minsta elementet har hittats placeras det i önskat läge.

hur man spelar en utorrent fil

Pseudokod för urvalssortering

Pseudokoden för urvalsorteringsalgoritmen ges nedan.

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)

Låt oss nu illustrera sorteringen av en matris med hjälp av urvalsortering.

Exempel på urvalssortering

Tänk på följande array som ska sorteras som ett exempel på en urvalsortering.

Exempel på urvalssortering

Pass 1

Pass 2

Pass 3

Pass 4

Nedan följer en tabellföreställning för illustrationen:

Osorterad listaMinsta elementSorterad lista
{17,10,7,29,2}två{}
{17,10,7,29}7{två}
{17,10,29}10{2.7}
{17.29}17{2,7,10)
{29}29{2,7,10,17}
{}{2,7,10,17,29}

Från illustrationen ser vi att vid varje pass sätts nästa minsta element i sin rätta position i den sorterade matrisen. Generellt sett behöver vi N-1-passeringar totalt för att sortera en matris av N-element.

Urval Sortera implementering i Java

Låt oss nu demonstrera Java-programmet för att implementera urvalsortering.

import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i

Produktion:

Originalmatris: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Sorterad matris: (2, 5, 7, 10, 15, 20, 23, 34, 42)

Output - Java-program för att implementera urvalsortering

I ovanstående java-exempel hittar vi upprepade gånger det minsta elementet i matrisen och placerar det i den sorterade matrisen tills hela matrisen är helt sorterad.

Urval Sortera länkad lista i Java

Nedan finns en länkad lista och vi måste sortera den med hjälp av urvalsortering. För att göra detta kommer vi att använda den rekursiva metoden för urvalsortering. Istället för att byta datadel av noden byter vi noder och justerar pekarna.

Så om den länkade listan ges enligt följande:

länkad lista

länkad lista - 2

Nedan följer Java-programmet som implementerar ovanstående sortering.

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

Produktion:

Originallänkad lista:
7 9 3 5 1 11
Länkad lista efter sortering:
1 3 5 7 9 11

Implementering av Java Sort - Output

Observera att i ovanstående program har vi omfördelat länkar till noder istället för att bara sortera datakomponenten i noden.

Vanliga frågor

F # 1) Hur fungerar urvalssortering?

Svar: Urvalsortering fungerar genom att underhålla två underarrayer. Minimumelementet från den osorterade undergruppen placeras i rätt position i en sorterad undergrupp. Sedan placeras det näst lägsta elementet i rätt läge. På så sätt sorteras hela matrisen genom att välja ett minimielement under varje iteration.

bästa programvaran för nedladdning av youtube-videor

F # 2) Vilken är komplexiteten i urvalsorteringen?

Svar: Den totala komplexiteten i urvalsorteringen är O (ntvå), vilket gör det till algoritmen som är ineffektiv på större datamängder. Andra sorteringstekniker är effektivare.

F # 3) Vilka är fördelarna och nackdelarna med urval?

Svar: Selektionssortering är sorteringstekniken på plats och därmed krävs det inte ytterligare lagring för att lagra mellanliggande element.

Det fungerar effektivt på mindre datastrukturer såväl som de datamängder som nästan är sorterade.

Den största nackdelen med urvalssorteringstekniken är att den fungerar mycket dåligt när storleken på datastrukturen ökar. Det blir inte bara långsammare utan minskar också effektiviteten.

F # 4) Hur många swappar finns det i sortimentet?

Svar: Urvalssorteringstekniken tar det minsta antalet byten. För bästa fall, när matrisen är sorterad, är antalet byten i urvalsorteringen 0.

F # 5) Sorteras urval snabbare än insättningssortering?

Svar: Insättningssorteringen är snabbare och effektivare och stabil. Urvalsortering är snabbare endast för mindre datamängder och delvis sorterade strukturer.

Slutsats

Selektionssortering är en teknik som fungerar genom att välja minimielementet medan du korsar matrisen. För varje pass / iteration väljs nästa minimielement i datamängden och placeras i rätt position.

Valssorteringstekniken fungerar effektivt när antalet element i datamängden är mindre, men den börjar fungera dåligt när storleken på datamängden växer. Det blir ineffektivt jämfört med andra liknande tekniker som insättningssortering.

I denna handledning har vi implementerat exempel för att sortera matriser och länkade listor med hjälp av urvalsortering.

=> Besök här för att se Java Training Series för alla.

Rekommenderad läsning

^