selection sort java selection sort algorithm examples
Acest tutorial va explica totul despre sortarea selecției în Java împreună cu algoritmul de sortare a selecției, codul Java, implementarea în Java și exemple Java:
Tehnica de sortare a selecției este o metodă în care cel mai mic element din matrice este selectat și schimbat cu primul element al matricei. Apoi, al doilea cel mai mic element din matrice este schimbat cu al doilea element și invers.
=> Verificați aici pentru a vedea A-Z a tutorialelor de instruire Java aici.
Ce veți învăța:
Selecție Sortare în Java
În acest fel, cel mai mic element din matrice este selectat în mod repetat și plasat în poziția corectă până când întregul tablou este sortat.
Două sub-tablouri sunt menținute pentru sortarea selecției:
- Sub-matrice sortate: În fiecare iterație, elementul minim este găsit și plasat în poziția corectă. Această sub-matrice este sortată.
- Sub-matrice nesortate: Celelalte elemente care nu sunt sortate.
Sortarea selecției este o tehnică de sortare simplă și simplă. Tehnica presupune doar găsirea celui mai mic element din fiecare trecere și plasarea acestuia în poziția corectă. Sortarea selecției este ideală pentru seturi de date mai mici, deoarece sortează eficient setul de date mai mic.
Astfel, putem spune că sortarea selecției nu este recomandabilă pentru liste mai mari de date.
Algoritm de sortare a selecției
Algoritmul general pentru sortarea selecției este dat mai jos:
Sortare selecție (A, N)
Pasul 1 : Repetați pașii 2 și 3 pentru K = 1 la N-1
Pasul 2 : Apelați cel mai mic de rutină (A, K, N, POS)
Pasul 3 :
Schimbați A (K) cu A (POS)
(Sfârșitul buclei)
Pasul 4 : IEȘIRE
Cel mai mic de rutină (A, K, N, POS)
Pasul 1 : (initialize) set smallestItem = A (K)
Pasul 2 : (inițializați) setați POS = K
Pasul 3 :
pentru J = K + 1 la N -1, repetați
ifest smallestItem> A (J)
set smallestItem = A (J)
set POS = J
(dacă sfârșitul)
(Sfârșitul buclei)
Pasul 4 : returnează POS
După cum puteți vedea, rutina pentru a găsi cel mai mic număr este apelată în timp ce parcurgeți setul de date. Odată găsit cel mai mic element, acesta este plasat în poziția dorită.
angularjs intervievează întrebări și răspunsuri pentru cei cu experiență în .net
Pseudocod pentru sortare selecție
Pseudo-codul pentru algoritmul de sortare a selecției este dat mai jos.
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) Să ilustrăm acum sortarea unui tablou folosind sortarea de selecție.
Selecție Exemplu de sortare
Luați în considerare următoarea matrice care urmează să fie sortată ca un exemplu de sortare de selecție.
Mai jos este prezentată o reprezentare tabelară pentru ilustrație:
Listă nesortată Cel mai mic element Listă sortată {17,10,7,29,2} Două {} {17,10,7,29} 7 {Două} {17,10,29} 10 {2.7} {17,29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
Din ilustrație, vedem că, la fiecare trecere, cel mai mic element următor este pus în poziția sa corectă în matricea sortată. În general, pentru a sorta o serie de N elemente, avem nevoie de N-1 treceri în total.
Selecție Sortare implementare în Java
Să demonstrăm acum programul Java pentru a implementa sortarea selecției.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Ieșire:
Matrice originală: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Matrice sortate: (2, 5, 7, 10, 15, 20, 23, 34, 42)
În exemplul Java de mai sus, găsim în mod repetat cel mai mic element din matrice și îl plasăm în matricea sortată până când întregul tablou este complet sortat.
Selecție Sortare listă legată în Java
Mai jos este o listă legată și trebuie să o sortăm folosind sortarea de selecție. Pentru a face acest lucru, vom folosi abordarea recursivă a sortării selecției. În loc să schimbăm partea de date a nodului, vom schimba nodurile și vom realinia indicii.
Deci, dacă lista legată este dată după cum urmează:
Dat mai jos este programul Java care implementează sortarea de mai sus.
// 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 Ieșire:
Lista originală legată:
7 9 3 5 1 11
Listă legată după sortare:
1 3 5 7 9 11
Rețineți că în programul de mai sus, am realiniat legăturile nodurilor în loc să sortăm doar componenta de date a nodului.
întrebări frecvente
Q # 1) Cum funcționează sortarea Selecției?
Răspuns: Sortarea selecției funcționează prin menținerea a două sub-tablouri. Elementul minim din subarray nesortat este plasat în poziția corectă într-un sub-array sortat. Apoi, cel de-al doilea element cel mai jos este plasat în poziția corectă. În acest fel, întreaga matrice este sortată selectând un element minim în timpul fiecărei iterații.
Q # 2) Care este complexitatea sortării selecției?
Răspuns: Complexitatea generală a sortării de selecție este O (nDouă), făcându-l astfel algoritmul care este ineficient pentru seturi de date mai mari. Alte tehnici de sortare sunt mai eficiente.
Q # 3) Care sunt avantajele și dezavantajele sortării selecției?
Răspuns: Sortarea prin selecție este tehnica de sortare la fața locului și, prin urmare, nu necesită stocare suplimentară pentru stocarea elementelor intermediare.
Funcționează eficient pe structuri de date mai mici, precum și pe seturile de date care sunt aproape sortate.
Dezavantajul major al tehnicii de sortare a selecției este că are performanțe foarte slabe pe măsură ce dimensiunea structurii datelor crește. Nu numai că devine mai lent, dar scade și eficiența.
Q # 4) Câte swap-uri există în sortarea selecției?
Răspuns: Tehnica de sortare a selecției ia numărul minim de swap-uri. În cel mai bun caz, atunci când matricea este sortată, numărul de swapuri din sortarea de selecție este 0.
Q # 5) Selecția este mai rapidă decât sortarea prin inserție?
Răspuns: Sortarea prin inserție este mai rapidă și mai eficientă, precum și stabilă. Sortarea selecției este mai rapidă doar pentru seturi de date mai mici și structuri parțial sortate.
Concluzie
Sortarea selecției este o tehnică care funcționează prin selectarea elementului minim în timp ce parcurgeți matricea. Pentru fiecare trecere / iterație, următorul element minim din setul de date este selectat și plasat în poziția corectă.
Tehnica de sortare a selecției funcționează eficient atunci când numărul de elemente din setul de date este mai mic, dar începe să funcționeze slab pe măsură ce dimensiunea setului de date crește. Devine ineficient în comparație cu alte tehnici similare, cum ar fi sortarea prin inserție.
exemple de minerit de date în lumea reală
În acest tutorial, am implementat exemple pentru sortarea matricelor și listelor legate folosind sortarea selecției.
=> Vizitați aici pentru a vedea seria de antrenament Java pentru toți.
Lectură recomandată
- Cum să sortați o matrice în Java - Tutorial cu exemple
- Selecție Sortare în C ++ cu exemple
- Tutorial Java Lungime matrice cu exemple de cod
- Metoda MongoDB Sort () cu exemple
- Matrice Jagged în Java - Tutorial cu exemple
- Comanda de sortare Unix cu sintaxă, opțiuni și exemple
- Inversați o matrice în Java - 3 metode cu exemple
- Tutorial JAVA pentru începători: peste 100 de cursuri video Java practice
