selection sort c with examples
Uno sguardo approfondito all'ordinamento della selezione in C ++ con esempi.
Come suggerisce il nome stesso, la tecnica di ordinamento della selezione seleziona prima l'elemento più piccolo dell'array e lo scambia con il primo elemento dell'array.
Successivamente, scambia il secondo elemento più piccolo dell'array con il secondo elemento e così via. Pertanto, per ogni passaggio, l'elemento più piccolo dell'array viene selezionato e messo nella posizione corretta finché l'intero array non viene ordinato.
=> Dai un'occhiata alla guida di formazione C ++ perfetta qui.
Cosa imparerai:
- introduzione
- Algoritmo generale
- Pseudocodice per l'ordinamento della selezione
- Illustrazione
- Esempio C ++
- Esempio Java
- Analisi della complessità dell'ordinamento di selezione
- Conclusione
- Lettura consigliata
introduzione
L'ordinamento di selezione è una tecnica di ordinamento abbastanza semplice poiché la tecnica prevede solo di trovare l'elemento più piccolo in ogni passaggio e posizionarlo nella posizione corretta.
L'ordinamento della selezione funziona in modo efficiente quando l'elenco da ordinare è di piccole dimensioni ma le sue prestazioni ne risentono negativamente poiché l'elenco da ordinare aumenta di dimensioni.
Quindi possiamo dire che l'ordinamento di selezione non è consigliabile per elenchi di dati più grandi.
Algoritmo generale
Di seguito è riportato l'algoritmo generale per l'ordinamento della selezione:
app per carte del tempo libero per iphone e android
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 del ciclo)
Passaggio 4 : USCITA
Routine più piccola (A, K, N, POS)
- Passo 1 : (initialize) set smallestElem = A (K)
- Passo 2 : (inizializza) imposta POS = K
- Passaggio 3 : per J = K + 1 a N -1, ripetere
se smallestElem> A (J)
set smallestElem = A (J)
impostare POS = J
(se finisce)
(Fine del ciclo) - Passaggio 4 : ritorno POS
Pseudocodice per ordinamento 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) Di seguito è riportato un esempio per illustrare questo algoritmo di ordinamento della selezione.
Illustrazione




La rappresentazione tabellare per questa illustrazione è mostrata di seguito:
Elenco non ordinato Minimo elemento Elenco ordinato {18,10,7,20,2} Due {} {18,10,7,20} 7 {Due} {18,10,20} 10 {2.7} {18.20} 18 {2,7,10) {venti} venti {2,7,10,18} {} {2,7,10,18,20}
Dall'illustrazione, vediamo che ad ogni passaggio il successivo elemento più piccolo viene messo nella sua posizione corretta nell'array ordinato. Dall'illustrazione sopra, vediamo che per ordinare un array di 5 elementi, erano necessarie quattro passate. Ciò significa in generale, per ordinare un array di N elementi, abbiamo bisogno di N-1 passaggi in totale.
Di seguito è riportata l'implementazione dell'algoritmo di ordinamento della selezione in C ++.
Esempio C ++
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<10;i++) { cout< Produzione:
Elenco di input degli elementi da ordinare
11 5 2 20 42 53 23 34101 22
L'elenco degli elementi ordinati è
2 5 11 20 22 23 34 42 53101
Numero di passaggi necessari per ordinare l'array: 10
Come mostrato nel programma precedente, iniziamo l'ordinamento della selezione confrontando il primo elemento dell'array con tutti gli altri elementi dell'array. Alla fine di questo confronto, l'elemento più piccolo dell'array viene posizionato nella prima posizione.
Nel passaggio successivo, utilizzando lo stesso approccio, l'elemento successivo più piccolo dell'array viene posizionato nella sua posizione corretta. Questo continua fino a N elementi o fino a quando l'intero array non viene ordinato.
Esempio Java
Successivamente, implementiamo la tecnica di ordinamento della selezione nel linguaggio Java.
class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println('
Input list to be sorted...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println('
printing sorted elements...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j) Produzione:
Elenco di input da ordinare ...
11 5 2 20 42 53 23 34101 22
stampa di elementi ordinati ...
2 5 11 20 22 23 34 42 53101
Anche nell'esempio Java sopra, applichiamo la stessa logica. Troviamo ripetutamente l'elemento più piccolo nell'array e lo inseriamo nell'array ordinato finché l'intero array non è completamente ordinato.
Pertanto, l'ordinamento della selezione è l'algoritmo più semplice da implementare poiché dobbiamo solo trovare ripetutamente l'elemento successivo più piccolo nell'array e scambiarlo con l'elemento nella posizione appropriata.
Analisi della complessità dell'ordinamento di selezione
Come visto nello pseudocodice sopra per l'ordinamento di selezione, sappiamo che l'ordinamento di selezione richiede due cicli for annidati l'uno con l'altro per completarsi. Un ciclo for passa attraverso tutti gli elementi nell'array e troviamo l'indice dell'elemento minimo usando un altro ciclo for che è annidato all'interno del ciclo for esterno.
Pertanto, data una dimensione N della matrice di input, l'algoritmo di ordinamento della selezione ha i seguenti valori di tempo e complessità.
Complessità temporale nel caso peggiore O (n 2); O (n) swap Migliore complessità temporale del caso O (n 2); O (n) swap Complessità temporale media O (n 2); O (n) swap Complessità spaziale O (1)
La complessità temporale di O ( n Due) è principalmente dovuto all'uso di due cicli for. Si noti che la tecnica di ordinamento per selezione non richiede mai più di O (n) scambi ed è vantaggiosa quando l'operazione di scrittura in memoria si rivela costosa.
Conclusione
L'ordinamento di selezione è un'altra tecnica di ordinamento più semplice che può essere facilmente implementata. L'ordinamento della selezione funziona meglio quando si conosce l'intervallo dei valori da ordinare. Quindi, per quanto riguarda l'ordinamento di strutture dati utilizzando l'ordinamento di selezione, possiamo ordinare solo strutture dati lineari e di dimensione finita.
Ciò significa che possiamo ordinare in modo efficiente le strutture di dati come gli array utilizzando l'ordinamento di selezione.
In questo tutorial, abbiamo discusso in dettaglio l'ordinamento della selezione, inclusa l'implementazione dell'ordinamento della selezione utilizzando i linguaggi C ++ e Java. La logica alla base dell'ordinamento della selezione è trovare ripetutamente l'elemento più piccolo nell'elenco e posizionarlo nella posizione corretta.
Nel prossimo tutorial, impareremo in dettaglio l'ordinamento per inserzione che si dice sia una tecnica più efficiente rispetto alle altre due tecniche che abbiamo discusso finora, ovvero l'ordinamento a bolle e l'ordinamento per selezione.
=> Controlla qui per vedere i tutorial di formazione dalla A alla Z di C ++ qui.
Lettura consigliata
- Ordinamento della shell in C ++ con esempi
- Metodo MongoDB Sort () con esempi
- Comando di ordinamento Unix con sintassi, opzioni ed esempi
- Bubble Sort in C ++ con esempi
- Ordinamento di inserzione in C ++ con esempi
- Unisci ordinamento in C ++ con esempi
- Ordinamento heap in C ++ con esempi
- Ordinamento rapido in C ++ con esempi