Menu

Výběr řazení v Javě - Algoritmus řazení a příklady

  • Hlavní
  • Jiný
  • Výběr řazení v Javě - Algoritmus řazení a příklady

selection sort java selection sort algorithm examples

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento výukový program vysvětlí vše o řazení řazení v Javě spolu s algoritmem řazení výběru, kódem Java, implementací v Javě a příklady Java:

Technika výběru výběru je metoda, při které je vybrán nejmenší prvek v poli a vyměněn za první prvek v poli. Dále se vymění druhý nejmenší prvek v poli s druhým prvkem a naopak.

=> Chcete-li vidět A-Z výukových kurzů Java zde, podívejte se sem.

Třídění výběru v Javě

Co se naučíte:

Výběr Seřadit v Javě

Tímto způsobem se opakovaně vybere nejmenší prvek v poli a umístí se do správné polohy, dokud se neuspořádá celé pole.

Pro třídění výběru jsou zachována dvě podskupiny:

  1. Seřazené podpole: V každé iteraci je minimální prvek nalezen a umístěn do správné polohy. Toto dílčí pole je tříděno.
  2. Netříděné podpole: Zbývající prvky, které nejsou seřazeny.

Výběr je přímá a snadná technika třídění. Tato technika zahrnuje pouze nalezení nejmenšího prvku v každém průchodu a jeho umístění do správné polohy. Výběr je ideální pro menší datové sady, protože efektivně třídí menší datovou sadu.

Můžeme tedy říci, že výběr není vhodný pro větší seznamy dat.

Algoritmus řazení

Obecný algoritmus pro třídění výběru je uveden níže:

Výběr řazení (A, N)

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

Krok 2 : Volejte rutinu nejmenší (A, K, N, POS)

Krok 3 :

Zaměňte A (K) za A (POS)
(Konec smyčky)

Krok 4 : KONEC

Rutina nejmenší (A, K, N, POS)

Krok 1 : (inicializovat) nastavit nejmenší položku = A (K)

Krok 2 : (inicializovat) nastavit POS = K

Krok 3 :

pro J = K + 1 až N -1, opakujte
pokud je nejmenší položka> A (J)
nastavit nejmenší položku = A (J)
nastavit POS = J
(pokud je konec)
(Konec smyčky)

Krok 4 : návrat POS

Jak vidíte, rutina hledání nejmenšího čísla se volá při procházení datovou sadou. Jakmile je nejmenší prvek nalezen, umístí se do požadované polohy.

jak přehrávat soubory .bin

Pseudokód pro výběr Seřadit

Níže je uveden pseudokód pro algoritmus třídění výběru.

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)

Pojďme si nyní ilustrovat třídění pole pomocí výběrového třídění.

Příklad řazení Výběr

Zvažte následující pole, které má být tříděno jako příklad řazení výběru.

Příklad řazení výběru

Projít 1

2. průchod

3. přihrávka

4. průchod

Níže je uvedena tabulka pro ilustraci:

Nezařazený seznamNejméně prvekSeřazený 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}

Z obrázku vidíme, že s každým průchodem je nejmenší prvek vložen do správné polohy v seřazeném poli. Obecně platí, že pro třídění řady N prvků potřebujeme celkem N-1 průchodů.

Implementace výběru výběru v Javě

Pojďme si nyní předvést program Java k implementaci třídění výběru.

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

Výstup:

Původní pole: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Řazené pole: (2, 5, 7, 10, 15, 20, 23, 34, 42)

Výstup - program Java pro implementaci třídění výběru

Ve výše uvedeném příkladu java opakovaně najdeme nejmenší prvek v poli a vložíme jej do seřazeného pole, dokud nebude celé pole zcela tříděno.

Výběr Seřadit propojený seznam v Javě

Níže je uveden propojený seznam a musíme jej třídit pomocí výběru řazení. K tomu použijeme rekurzivní přístup řazení výběru. Místo toho, abychom vyměnili datovou část uzlu, vyměníme uzly a srovnáme ukazatele.

Pokud je tedy propojený seznam uveden následovně:

spojový seznam

propojený seznam - 2

Níže je uveden program Java, který implementuje výše uvedené třídění.

// 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ýstup:

Původní propojený seznam:
7 9 3 5 1 11
Propojený seznam po seřazení:
1 3 5 7 9 11

Implementace Java Sort - výstup

Všimněte si, že ve výše uvedeném programu jsme místo třídění pouze datové komponenty uzlu změnili uspořádání uzlů.

Často kladené otázky

Otázka č. 1) Jak funguje výběrové třídění?

Odpovědět: Třídění výběru funguje udržováním dvou dílčích polí. Minimální prvek z netříděného dílčího pole je umístěn na správné místo v seřazeném dílčím poli. Poté je druhý nejnižší prvek umístěn do správné polohy. Tímto způsobem je celé pole tříděno výběrem minimálního prvku během každé iterace.

Otázka č. 2) Jaká je složitost druhu výběru?

Odpovědět: Celková složitost výběru je O (ndva), čímž se stává algoritmem, který je neúčinný na větších souborech dat. Efektivnější jsou další techniky třídění.

Otázka č. 3) Jaké jsou výhody a nevýhody výběru?

Odpovědět: Třídění výběru je technika třídění na místě, a proto nevyžaduje další úložiště k ukládání mezilehlých prvků.

Funguje efektivně na menších datových strukturách i na datových sadách, které jsou téměř seřazeny.

Hlavní nevýhodou techniky třídění výběru je to, že funguje velmi špatně, jak se zvětšuje velikost datové struktury. Nejenže se zpomaluje, ale také snižuje účinnost.

Otázka č. 4) Kolik swapů je v Selection sort?

Odpovědět: Technika třídění výběru vyžaduje minimální počet swapů. V nejlepším případě, když je pole seřazeno, je počet swapů ve výběru výběr 0.

dotazy na server SQL Server pro zkušené profesionály

Otázka č. 5) Je výběr řazení rychlejší než vložení?

Odpovědět: Třídění vložení je rychlejší a efektivnější a také stabilní. Třídění výběru je rychlejší pouze pro menší datové sady a částečně tříděné struktury.

Závěr

Třídění výběru je technika, která funguje tak, že se při procházení pole vybere minimální prvek. Pro každý průchod / iteraci je vybrán další minimální prvek v datové sadě a umístěn do správné polohy.

Technika řazení výběru funguje efektivně, když je počet prvků v datové sadě menší, ale začne růst špatně, jak roste velikost datové sady. Ve srovnání s jinými podobnými technikami, jako je řazení, se stává neúčinným.

V tomto kurzu jsme implementovali příklady řazení polí a propojených seznamů pomocí řazení výběru.

=> Navštivte zde a prohlédněte si sérii školení Java pro všechny.

Doporučené čtení

^