selection sort java selection sort algorithm examples
Ta vadnica bo razložila vse o razvrstitvenem razvrščanju v Javi, skupaj z algoritmom izbirnega razvrščanja, kodo Java, implementacijo v javi in zgledih Java:
Izbirna tehnika razvrščanja je metoda, pri kateri je izbran najmanjši element v matriki in zamenjan s prvim elementom matrike. Nato se drugi najmanjši element v matriki zamenja z drugim elementom in obratno.
=> Tukaj si oglejte A-Z vadnic za učenje Java.
Kaj se boste naučili:
Razvrstitev izbora v Javi
Na ta način je najmanjši element v matriki večkrat izbran in postavljen v njegov pravilen položaj, dokler ni razvrščena celotna matrika.
Za razvrščanje izbire se ohranita dva podniza:
- Razvrščeno podniz: V vsaki ponovitvi najdemo najmanjši element in ga postavimo v svoj pravilen položaj. Ta podniz je razvrščen.
- Nerazvrščena pod matrika: Preostali elementi, ki niso razvrščeni.
Razvrščanje je preprosta in enostavna tehnika razvrščanja. Tehnika vključuje le iskanje najmanjšega elementa pri vsakem podajanju in postavitev v pravi položaj. Izbirno razvrščanje je idealno za manjše nabore podatkov, saj učinkovito razvršča manjši nabor podatkov.
Tako lahko rečemo, da izbira vrst ni priporočljiva za večje sezname podatkov.
Algoritem sortiranja izbora
Splošni algoritem za izbirno razvrščanje je podan spodaj:
Razvrstitev izbora (A, N)
Korak 1 : Ponovite 2. in 3. korak za K = 1 do N-1
2. korak : Najmanjša rutina klica (A, K, N, POS)
3. korak :
Zamenjajte A (K) z A (POS)
(Konec zanke)
4. korak : EXIT
Redno najmanjše (A, K, N, POS)
Korak 1 : (inicializiraj) nastavi najmanjši element = A (K)
2. korak : (inicializiraj) nastavi POS = K
3. korak :
za J = K + 1 do N -1, ponovite
če je najmanjši element> A (J)
nastavi najmanjši element = A (J)
nastavite POS = J
(če je konec)
(Konec zanke)
4. korak : vrnitev POS
Kot lahko vidite, se med prehodom po naboru podatkov pokliče rutina za iskanje najmanjšega števila. Ko najdete najmanjši element, ga postavite v želeni položaj.
mobilni telefon vohun app za android
Psevkodo za sortiranje izbire
Psevdo-koda za algoritem za izbiro razvrščanja je podana spodaj.
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) Ponazorimo zdaj razvrščanje matrike z uporabo izbirnega razvrščanja.
Primer sortiranja izbora
Naslednjo matriko, ki jo je treba razvrstiti, upoštevajte kot primer razvrščanja po izboru.
Spodaj je tabelarična predstavitev za ponazoritev:
Nerazvrščen seznam Najmanj element Razvrščen seznam {17,10,7,29,2} dva {} {17,10,7,29} 7. {dva} {17,10,29} 10. {2,7} {17,29} 17. {2,7,10) {29} 29. {2,7,10,17} {} {2,7,10,17,29}
Na sliki vidimo, da je z vsakim prehodom naslednji najmanjši element postavljen v svoj pravilen položaj v razvrščeni matriki. Na splošno za razvrščanje nabora N elementov potrebujemo skupaj N-1 prehodov.
Izvedba razvrščanja v Java
Pokažimo zdaj program Java za izvedbo razvrščanja izbir.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Izhod:
Izvirno polje: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Razvrščeno polje: (2, 5, 7, 10, 15, 20, 23, 34, 42)
V zgornjem primeru Java večkrat najdemo najmanjši element v matriki in ga damo v razvrščeno polje, dokler ni celotno polje popolnoma razvrščeno.
Izbrani razvrsti povezani seznam v Javi
Spodaj je povezan seznam in ga moramo razvrstiti s pomočjo izbirnega razvrščanja. Za to bomo uporabili rekurzivni pristop izbiranja. Namesto da zamenjamo podatkovni del vozlišča, bomo vozlišča zamenjali in kazalce poravnali.
Torej, če je povezan seznam naveden na naslednji način:
Spodaj je program Java, ki izvaja zgornje razvrščanje.
// 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 Izhod:
Prvotno povezan seznam:
7 9 3 5 1 11
Po razvrščanju povezan seznam:
1 3 5 7 9 11
Upoštevajte, da smo v zgornjem programu preuredili povezave vozlišč, namesto da bi razvrstili samo podatkovno komponento vozlišča.
Pogosto zastavljena vprašanja
V # 1) Kako deluje sortiranje izbora?
Odgovor: Razvrščanje izbora deluje tako, da vzdržuje dva podniz. Najmanjši element iz nesortirane podmreže je postavljen na svoj pravilen položaj v razvrščeni podniz. Nato se drugi najnižji element postavi v pravi položaj. Na ta način se celotno polje razvrsti tako, da se med vsako ponovitvijo izbere najmanjši element.
V # 2) Kakšna je zapletenost sorte Selection?
analiza vzrokov pri testiranju programske opreme
Odgovor: Celotna zapletenost izbire je O (ndva), s čimer je algoritem neučinkovit pri večjih naborih podatkov. Druge tehnike razvrščanja so učinkovitejše.
3. vprašanje) Katere so prednosti in slabosti izbire?
Odgovor: Izbirno razvrščanje je tehnika sortiranja na mestu, zato za shranjevanje vmesnih elementov ne potrebuje dodatnega pomnilnika.
Učinkovito deluje tako na manjših podatkovnih strukturah kot tudi na vrstah podatkov, ki so skoraj razvrščene.
Glavna pomanjkljivost tehnike razvrščanja je, da deluje zelo slabo, ko se velikost podatkovne strukture poveča. Ne samo, da postane počasnejši, ampak tudi zmanjša učinkovitost.
V # 4) Koliko zamenjav je v razvrstitvi Selection?
Odgovor: Izbirna tehnika razvrščanja zavzame minimalno število zamenjav. V najboljšem primeru je pri zamenjavi polja število zamenjav v izbirnem razvrščanju 0.
V # 5) Ali je izbor razvrščen hitreje kot vstavljanje?
Odgovor: Razvrstitev vstavljanja je hitrejša in učinkovitejša ter stabilna. Razvrščanje izbora je hitrejše le za manjše nabore podatkov in delno razvrščene strukture.
Zaključek
Izbirno razvrščanje je tehnika, ki deluje tako, da med prečkanjem polja izbere najmanjši element. Za vsak prehod / ponovitev se izbere naslednji najmanjši element v naboru podatkov in postavi v svoj pravilen položaj.
Izbirna tehnika razvrščanja deluje učinkovito, kadar je število elementov v naboru podatkov manjše, vendar začne delovati slabo, ko velikost nabora podatkov narašča. V primerjavi z drugimi podobnimi tehnikami, kot je vstavljanje, postane neučinkovit.
V tej vadnici smo izvedli primere za razvrščanje nizov in povezanih seznamov z uporabo izbirnega razvrščanja.
=> Obiščite tukaj in si oglejte serijo Java Training for All.
Priporočeno branje
- Kako razvrstiti polje v Javi - Vadnica s primeri
- Izbirno razvrščanje v C ++ z primeri
- Vadnica za dolžino polja Java s primeri kode
- Metoda sortiranja () MongoDB () s primeri
- Nazobčan niz v Javi - Vadnica s primeri
- Ukaz za razvrščanje Unix s sintakso, možnostmi in primeri
- Obrni matriko v Javi - 3 metode s primeri
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
