Menu

Výberové triedenie v Jave - Algoritmus a výberové triedenie výberu

  • Hlavná
  • Iné
  • Výberové triedenie v Jave - Algoritmus a výberové triedenie výberu

selection sort java selection sort algorithm examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

V tomto výučbe sa dozviete všetko o triedení výberu v Jave spolu s algoritmom výberu triedenia, kóde Java, implementácii v Jave a príkladoch Javy:

Technika triedenia výberu je metóda, pri ktorej sa vyberie najmenší prvok v poli a zamení sa s prvým prvkom poľa. Ďalej sa vymení druhý najmenší prvok v poli s druhým prvkom a naopak.

=> Tu nájdete A-Z výučbových kurzov Java.

Zoradenie výberu v Jave

Čo sa dozviete:

Výber Zoradiť v Jave

Týmto spôsobom sa opakovane vyberie najmenší prvok v poli a umiestni sa na správne miesto, kým sa celé pole nezoradí.

Pre triedenie výberu sú zachované dve podradené polia:

  1. Zoradené čiastkové pole: V každej iterácii je minimálny prvok nájdený a umiestnený na správnom mieste. Toto čiastkové pole je zoradené.
  2. Netriedené čiastkové pole: Zvyšné prvky, ktoré nie sú zoradené.

Výber je ľahká a jednoduchá technika triedenia. Táto technika spočíva iba v nájdení najmenšieho prvku v každom prechode a jeho umiestnení do správnej polohy. Výber je ideálny pre menšie množiny údajov, pretože efektívne triedi menšie množiny údajov.

Môžeme teda povedať, že pre väčšie zoznamy údajov nie je vhodné výberové triedenie.

Algoritmus triedenia výberu

Všeobecný algoritmus pre zoradenie podľa výberu je uvedený nižšie:

Zoradenie podľa výberu (A, N)

Krok 1 : Opakujte kroky 2 a 3 pre K = 1 až N-1

Krok 2 : Volajte najmenšiu rutinu (A, K, N, POS)

Krok 3 :

Zamieňajte A (K) s A (POS)
(Koniec slučky)

Krok 4 : VÝCHOD

Rutina najmenšia (A, K, N, POS)

Krok 1 : (inicializovať) nastaviť najmenšiu položku = A (K)

Krok 2 : (inicializovať) nastaviť POS = K

Krok 3 :

pre J = K + 1 až N -1, opakujte
ak je najmenšia položka> A (J)
nastaviť najmenšiu položku = A (J)
nastaviť POS = J
(ak je koniec)
(Koniec slučky)

Krok 4 : spiatočný POS

Ako vidíte, rutina hľadania najmenšieho čísla sa volá pri prechádzaní množinou údajov. Len čo sa nájde najmenší prvok, umiestni sa do požadovanej polohy.

dijkstraov algoritmus používajúci prioritnú frontu java

Pseudokód na výber Zoradiť

Pseudokód pre algoritmus výberu je uvedený nižšie.

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)

Poďme si teraz ilustrovať triedenie poľa pomocou výberového triedenia.

Príklad triedenia výberu

Zvážte nasledujúce pole, ktoré sa má zoradiť ako príklad zoradenia podľa výberu.

Príklad triedenia výberu

Prejdite 1

Prejdite 2.

Prejdite 3.

Prejdite 4.

Ďalej je uvedená tabuľková reprezentácia ilustrácie:

Netriedený zoznamNajmenej prvokZoradený zoznam
{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}

Z ilustrácie vidíme, že pri každom prechode sa ďalší najmenší prvok v zoradenom poli umiestni na správnu pozíciu. Všeobecne platí, že na roztriedenie poľa N prvkov potrebujeme celkovo N-1 prechodov.

Implementácia triedenia výberu v Jave

Teraz si ukážeme program Java na implementáciu triedenia výberu.

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

Výkon:

Originálne pole: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Zoradené pole: (2, 5, 7, 10, 15, 20, 23, 34, 42)

Výstup - program Java na implementáciu výberu

Vo vyššie uvedenom príklade Java opakovane nájdeme najmenší prvok v poli a vložíme ho do zoradeného poľa, kým nebude celé pole úplne zoradené.

Výber Zoradiť prepojený zoznam v Jave

Nižšie je uvedený prepojený zoznam a musíme ho zoradiť pomocou výberu. K tomu použijeme rekurzívny prístup triedenia výberu. Namiesto výmeny dátovej časti uzla zameníme uzly a znova nastavíme ukazovatele.

Ak je teda prepojený zoznam uvedený takto:

prepojený zoznam

prepojený zoznam - 2

Ďalej je uvedený program Java, ktorý implementuje vyššie uvedené triedenie.

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

Výkon:

Pôvodný prepojený zoznam:
7 9 3 5 1 11
Prepojený zoznam po zoradení:
1 3 5 7 9 11

Implementácia Java Sort - výstup

Všimnite si, že vo vyššie uvedenom programe sme namiesto triedenia iba dátovej zložky uzla usporiadali odkazy uzlov.

často kladené otázky

Otázka č. 1) Ako funguje výberové triedenie?

Odpoveď: Výberové triedenie funguje zachovaním dvoch podradených polí. Minimálny prvok z netriedeného podradeného poľa je umiestnený na svojom správnom mieste v zoradenom čiastkovom poli. Potom sa druhý najnižší prvok umiestni do svojej správnej polohy. Týmto spôsobom je celé pole zoradené výberom minimálneho prvku počas každej iterácie.

Otázka č. 2) Aká je zložitosť druhu výberu?

Odpoveď: Celková zložitosť výberu je O (ndva), čím sa stáva algoritmom neúčinným pre väčšie súbory údajov. Efektívnejšie sú iné techniky triedenia.

Otázka č. 3) Aké sú výhody a nevýhody výberu?

aký je najlepší sťahovač mp3 pre Android

Odpoveď: Výberové triedenie je technika triedenia na mieste, a preto nevyžaduje ďalšie ukladanie na ukladanie medziľahlých prvkov.

Funguje efektívne na menších údajových štruktúrach, ako aj na množinách údajov, ktoré sú takmer zoradené.

Hlavnou nevýhodou techniky výberu je, že pri zvyšovaní veľkosti dátovej štruktúry funguje veľmi zle. Nielenže sa spomalí, ale aj zníži účinnosť.

Otázka č. 4) Koľko swapov je v Selection sorte?

Odpoveď: Technika triedenia výberu vyžaduje minimálny počet výmen. V najlepšom prípade, keď je pole zoradené, je počet swapov v zoradení výberu 0.

Otázka č. 5) Je výber triedený rýchlejšie ako vloženie?

Odpoveď: Triedenie vloženia je rýchlejšie a efektívnejšie, rovnako ako stabilné. Zoradenie podľa výberu je rýchlejšie iba pre menšie súbory údajov a čiastočne triedené štruktúry.

Záver

Výberové triedenie je technika, ktorá funguje tak, že sa pri prechode po poli vyberá minimálny prvok. Pre každé absolvovanie / iteráciu sa vyberie ďalší minimálny prvok v množine údajov a umiestni sa na správne miesto.

Technika triedenia výberu funguje efektívne, keď je počet prvkov v množine údajov menší, ale s rastúcou veľkosťou množiny údajov začne fungovať zle. V porovnaní s inými podobnými technikami, ako je napríklad vkladanie, sa stáva neefektívnym.

V tomto tutoriáli sme implementovali príklady triedenia polí a prepojených zoznamov pomocou triedenia výberu.

=> Navštívte tu a pozrite si sériu školení Java pre všetkých.

Odporúčané čítanie

^