selection sort java selection sort algorithm examples
Questo tutorial spiegherà tutto sull'ordinamento della selezione in Java insieme all'algoritmo di ordinamento della selezione, al codice Java, all'implementazione in Java e agli esempi Java:
La tecnica di ordinamento della selezione è un metodo in cui l'elemento più piccolo dell'array viene selezionato e scambiato con il primo elemento dell'array. Successivamente, il secondo elemento più piccolo dell'array viene scambiato con il secondo elemento e viceversa.
=> Controlla qui per vedere qui i tutorial di formazione su Java dalla A alla Z.
Cosa imparerai:
Ordina selezione in Java
In questo modo l'elemento più piccolo dell'array viene selezionato ripetutamente e messo nella sua posizione corretta fino a quando l'intero array viene ordinato.
Vengono mantenuti due sotto-array per l'ordinamento della selezione:
- Sotto-array ordinato: In ogni iterazione, l'elemento minimo viene trovato e posizionato nella sua posizione corretta. Questo sotto-array è ordinato.
- Sotto-array non ordinato: Gli elementi rimanenti non ordinati.
L'ordinamento di selezione è una tecnica di ordinamento semplice e diretta. La tecnica consiste solo nel trovare l'elemento più piccolo in ogni passaggio e posizionarlo nella posizione corretta. L'ordinamento di selezione è ideale per i set di dati più piccoli poiché ordina i set di dati più piccoli in modo efficiente.
Quindi possiamo dire che l'ordinamento della selezione non è consigliabile per elenchi di dati più grandi.
Algoritmo di ordinamento della selezione
Di seguito viene fornito l'algoritmo generale per l'ordinamento della selezione:
Ordinamento selezione (A, N)
Passo 1 : Ripetere i passaggi 2 e 3 per K = da 1 a N-1
Passo 2 : Chiama la routine più piccola (A, K, N, POS)
Passaggio 3 :
Scambia A (K) con A (POS)
(Fine ciclo)
Passaggio 4 : USCITA
Routine più piccola (A, K, N, POS)
Passo 1 : (initialize) set smallestItem = A (K)
Passo 2 : (inizializza) imposta POS = K
Passaggio 3 :
per J = K + 1 a N -1, ripetere
se smallestItem> A (J)
set smallestItem = A (J)
impostare POS = J
(se finisce)
(Fine ciclo)
Passaggio 4 : ritorno POS
Come puoi vedere, la routine per trovare il numero più piccolo viene chiamata durante l'attraversamento del set di dati. Una volta trovato l'elemento più piccolo, viene posizionato nella posizione desiderata.
java come rimuovere un elemento da un array
Pseudocodice per l'ordinamento della selezione
Di seguito viene fornito lo pseudo codice per l'algoritmo di ordinamento della selezione.
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) Vediamo ora di illustrare l'ordinamento di un array utilizzando l'ordinamento di selezione.
Esempio di ordinamento della selezione
Considera il seguente array che deve essere ordinato come esempio di un ordinamento di selezione.
Di seguito è riportata una rappresentazione tabellare per l'illustrazione:
Elenco non ordinato Minimo elemento Elenco ordinato {17,10,7,29,2} Due {} {17,10,7,29} 7 {Due} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
Dall'illustrazione, vediamo che ad ogni passaggio il successivo elemento più piccolo viene messo nella sua posizione corretta nell'array ordinato. In generale, per ordinare un array di N elementi, abbiamo bisogno di N-1 passaggi in totale.
Implementazione dell'ordinamento di selezione in Java
Dimostriamo ora il programma Java per implementare l'ordinamento di selezione.
come riprodurre file flash Shockwave
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Produzione:
Array originale: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Array ordinato: (2, 5, 7, 10, 15, 20, 23, 34, 42)
Nell'esempio java sopra, troviamo ripetutamente l'elemento più piccolo nell'array e lo inseriamo nell'array ordinato fino a quando l'intero array non è completamente ordinato.
Selezione Ordina elenco collegato in Java
Di seguito è riportato un elenco collegato e dobbiamo ordinarlo utilizzando l'ordinamento di selezione. Per fare ciò useremo l'approccio ricorsivo dell'ordinamento per selezione. Invece di scambiare la parte dati del nodo, cambieremo i nodi e riallineamo i puntatori.
Quindi, se l'elenco collegato viene fornito come segue:
Di seguito è riportato il programma Java che implementa l'ordinamento di cui sopra.
// 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 Produzione:
Elenco collegato originale:
7 9 3 5 1 11
Elenco collegato dopo l'ordinamento:
1 3 5 7 9 11
Si noti che nel programma precedente, abbiamo riallineato i collegamenti dei nodi invece di ordinare solo il componente dati del nodo.
Domande frequenti
D # 1) Come funziona l'ordinamento della selezione?
Risposta: L'ordinamento della selezione funziona mantenendo due sotto-array. L'elemento minimo dal sottoarray non ordinato viene posizionato nella sua posizione corretta in un sotto-array ordinato. Quindi il secondo elemento più basso viene posizionato nella sua posizione corretta. In questo modo, l'intero array viene ordinato selezionando un elemento minimo durante ogni iterazione.
Q # 2) Qual è la complessità dell'ordinamento di selezione?
Risposta: La complessità complessiva dell'ordinamento della selezione è O (nDue), rendendolo così l'algoritmo inefficiente su set di dati più grandi. Altre tecniche di ordinamento sono più efficienti.
Q # 3) Quali sono i vantaggi e gli svantaggi dell'ordinamento di selezione?
Risposta: L'ordinamento di selezione è la tecnica di ordinamento sul posto e quindi non richiede memoria aggiuntiva per memorizzare gli elementi intermedi.
Funziona in modo efficiente su strutture di dati più piccole e su set di dati quasi ordinati.
Il principale svantaggio della tecnica di ordinamento della selezione è che funziona molto male all'aumentare della dimensione della struttura dei dati. Non solo diventa più lento, ma diminuisce anche l'efficienza.
Q # 4) Quanti scambi ci sono nell'ordinamento Selezione?
Risposta: La tecnica di ordinamento della selezione accetta il numero minimo di scambi. Nel migliore dei casi, quando l'array è ordinato, il numero di scambi nell'ordinamento della selezione è 0.
Q # 5) L'ordinamento della selezione è più veloce dell'ordinamento per inserzione?
Risposta: L'ordinamento per inserzione è più veloce, efficiente e stabile. L'ordinamento della selezione è più veloce solo per set di dati più piccoli e strutture parzialmente ordinate.
Conclusione
L'ordinamento della selezione è una tecnica che funziona selezionando l'elemento minimo mentre si attraversa l'array. Per ogni passaggio / iterazione, l'elemento minimo successivo nel set di dati viene selezionato e posizionato nella posizione corretta.
La tecnica di ordinamento della selezione funziona in modo efficiente quando il numero di elementi nel set di dati è inferiore, ma inizia a funzionare male con l'aumentare delle dimensioni del set di dati. Diventa inefficiente rispetto ad altre tecniche simili come l'ordinamento per inserzione.
In questo tutorial, abbiamo implementato esempi per ordinare array ed elenchi collegati utilizzando l'ordinamento di selezione.
=> Visita qui per vedere la serie di formazione Java per tutti.
Lettura consigliata
- Come ordinare un array in Java - Tutorial con esempi
- Ordinamento di selezione in C ++ con esempi
- Tutorial sulla lunghezza di array Java con esempi di codice
- Metodo MongoDB Sort () con esempi
- Jagged Array in Java - Tutorial con esempi
- Comando di ordinamento Unix con sintassi, opzioni ed esempi
- Invertire un array in Java - 3 metodi con esempi
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
