Meni

Sortiranje odabira na Javi - Algoritam sortiranja odabira i primjeri

  • Glavni
  • Ostalo
  • Sortiranje odabira na Javi - Algoritam sortiranja odabira i primjeri

selection sort java selection sort algorithm examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj će vodič objasniti sve o sortiranju izbora u Javi, zajedno s algoritmom sortiranja izbora, Java kodom, primjenom u Javi i Java primjerima:

Tehnika sortiranja odabira je metoda u kojoj se odabire najmanji element u nizu i zamjenjuje s prvim elementom niza. Dalje, drugi najmanji element u polju mijenja se s drugim elementom i obrnuto.

=> Ovdje pogledajte kako biste ovdje vidjeli A-Z Java Vodiča za obuku.

Sortiranje izbora u Javi

Što ćete naučiti:

Sortiranje izbora u Javi

Na taj se način najmanji element u polju više puta odabire i stavlja u svoj odgovarajući položaj dok se cijeli niz ne sortira.

Za sortiranje odabira održavaju se dva podniza:

  1. Razvrstani podniz: U svakoj iteraciji pronalazi se minimalni element koji se postavlja u svoj odgovarajući položaj. Ovaj je pod-niz sortiran.
  2. Nerazvrstani podniz: Preostali elementi koji nisu razvrstani.

Razvrstavanje je jednostavna i jednostavna tehnika sortiranja. Tehnika uključuje samo pronalaženje najmanjeg elementa u svakom dodavanju i postavljanje u točan položaj. Razvrstavanje odabira idealno je za manje skupove podataka jer učinkovito sortira manji skup podataka.

Stoga možemo reći da sortiranje odabira nije poželjno za veće popise podataka.

Algoritam sortiranja odabira

Opći algoritam za sortiranje odabira dan je u nastavku:

Sortiranje odabira (A, N)

Korak 1 : Ponovite korake 2 i 3 za K = 1 do N-1

Korak 2 : Najmanja rutina poziva (A, K, N, POS)

3. korak :

Zamijenite A (K) s A (POS)
(Kraj petlje)

4. korak : IZLAZ

Rutinski najmanji (A, K, N, POS)

Korak 1 : (inicijaliziraj) postavi najmanjiItem = A (K)

Korak 2 : (inicijalizacija) postavite POS = K

3. korak :

za J = K + 1 do N -1, ponovite
ako je najmanjiItem> A (J)
postavi najmanjiIst = A (J)
postavite POS = J
(ako je kraj)
(Kraj petlje)

4. korak : povrat POS

Kao što vidite, tijekom prelaska skupa podataka poziva se rutina za pronalaženje najmanjeg broja. Nakon što se pronađe najmanji element, postavlja se u željeni položaj.

dijkstrin algoritam koji koristi prioritetni red java

Pseudocode za sortiranje odabira

Pseudo-kôd za algoritam sortiranja odabira dan je u nastavku.

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)

Pokažimo sada sortiranje niza pomoću selekcijskog sortiranja.

Primjer sortiranja odabira

Razmotrite sljedeći niz koji će se sortirati kao primjer sortiranja odabira.

Primjer sortiranja odabira

Prolaz 1

Prolaz 2

Prolaz 3

Prolaz 4

Dolje je tablični prikaz za ilustraciju:

Nesortirani popisNajmanje elementaPoredani popis
{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}

Iz ilustracije vidimo da se pri svakom prolazu sljedeći najmanji element stavlja u svoj ispravan položaj u razvrstanom nizu. Općenito, za sortiranje niza od N elemenata trebaju nam ukupno N-1 prolazi.

Implementacija sortiranja izbora u Javi

Pokažimo sada program Java za implementaciju sortiranja odabira.

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

Izlaz:

Izvorni niz: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Sortirani niz: (2, 5, 7, 10, 15, 20, 23, 34, 42)

Izlaz - Java program za provedbu sortiranja odabira

U gore navedenom primjeru jave, više puta pronalazimo najmanji element u polju i stavljamo ga u razvrstani niz dok se cijeli niz potpuno ne sortira.

Izbor Poredaj povezani popis u Javi

Dolje je povezani popis i moramo ga sortirati pomoću selekcijskog sortiranja. Da bismo to učinili, poslužit ćemo se rekurzivnim pristupom sortiranja odabira. Umjesto da zamijenimo podatkovni dio čvora, zamijenit ćemo čvorove i preusmjeriti pokazivače.

Dakle, ako je povezani popis dat na sljedeći način:

povezani popis

povezani popis - 2

Dolje je dan Java program koji provodi gore navedeno sortiranje.

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

Izlaz:

Izvorni povezani popis:
7 9 3 5 1 11
Povezani popis nakon sortiranja:
1 3 5 7 9 11

Implementacija Java Sortiranje - Izlaz

Imajte na umu da smo u gornjem programu poravnali veze čvorova umjesto da sortiramo samo podatkovnu komponentu čvora.

kako otvoriti apk datoteku

Često postavljana pitanja

P # 1) Kako funkcionira sortiranje odabira?

Odgovor: Razvrstavanje odabira funkcionira održavanjem dva podniza. Minimalni element iz nerazvrstane podniza postavlja se u svoj odgovarajući položaj u razvrstani podniz. Tada se drugi najniži element postavlja u pravilan položaj. Na taj se način cijeli niz sortira odabirom minimalnog elementa tijekom svake iteracije.

P # 2) Koja je složenost selekcijske sorte?

Odgovor: Ukupna složenost selekcijske sorte je O (ndva), što ga čini algoritmom koji je neučinkovit za veće skupove podataka. Ostale su tehnike sortiranja učinkovitije.

3. pitanje) Koje su prednosti i nedostaci vrste odabira?

Odgovor: Selekcijsko sortiranje je tehnika sortiranja na mjestu i stoga ne zahtijeva dodatni prostor za pohranu posrednih elemenata.

Učinkovito djeluje na manjim strukturama podataka, kao i na skupovima podataka koji su gotovo sortirani.

Glavni nedostatak selekcijske tehnike sortiranja je taj što se vrlo loše izvodi s povećanjem veličine strukture podataka. Ne samo da postaje sporiji već smanjuje i učinkovitost.

P # 4) Koliko zamjena postoji u sortiranju Odabir?

Odgovor: Tehnika sortiranja odabirom uzima minimalan broj zamjena. U najboljem slučaju, kada se niz sortira, broj zamjena u sortiranju odabira je 0.

P # 5) Je li sortiranje izbora brže od sortiranja umetanjem?

Odgovor: Razvrstavanje umetanja je brže i učinkovitije te stabilno. Sortiranje izbora brže je samo za manje skupove podataka i djelomično sortirane strukture.

Zaključak

Sortiranje odabira je tehnika koja funkcionira odabirom minimalnog elementa tijekom prolaska nizom. Za svaki prolaz / iteraciju odabire se sljedeći minimalni element u skupu podataka i postavlja se u njegov odgovarajući položaj.

Tehnika sortiranja odabirom djeluje učinkovito kada je broj elemenata u skupu podataka manji, ali počinje loše funkcionirati kako veličina skupa podataka raste. Postaje neučinkovit u usporedbi s drugim sličnim tehnikama poput umetanja.

U ovom smo uputstvu implementirali primjere za sortiranje nizova i povezanih popisa pomoću selekcijskog sortiranja.

=> Posjetite ovdje da biste vidjeli seriju Java treninga za sve.

Preporučena literatura

^