In questo tutorial imparerai come funziona l'ordinamento della selezione. Inoltre, troverai esempi funzionanti di ordinamento di selezione in C, C ++, Java e Python.
L'ordinamento di selezione è un algoritmo che seleziona l'elemento più piccolo da un elenco non ordinato in ogni iterazione e posiziona quell'elemento all'inizio dell'elenco non ordinato.
Come funziona l'ordinamento della selezione?
- Imposta il primo elemento come
minimum.
Seleziona il primo elemento come minimo - Confronta
minimumcon il secondo elemento. Se il secondo elemento è più piccolo diminimum, assegna il secondo elemento comeminimum.
Confrontaminimumcon il terzo elemento. Anche in questo caso, se il terzo elemento è più piccolo, assegnareminimumal terzo elemento altrimenti non fare nulla. Il processo va avanti fino all'ultimo elemento.
Confronta il minimo con gli elementi rimanenti - Dopo ogni iterazione,
minimumviene posizionato all'inizio dell'elenco non ordinato.
Scambia il primo con il minimo - Per ogni iterazione, l'indicizzazione inizia dal primo elemento non ordinato. I passaggi da 1 a 3 vengono ripetuti fino a quando tutti gli elementi sono posizionati nelle posizioni corrette.
La prima iterazione 
La seconda iterazione 
La terza iterazione 
La quarta iterazione
Algoritmo di ordinamento della selezione
selectionSort (array, size) repeat (size - 1) times imposta il primo elemento non ordinato come minimo per ciascuno degli elementi non ordinati se elemento <currentMinimum imposta l'elemento come nuovo minimo minimo di scambio con la prima posizione non ordinata fine selezione
Esempi di Python, Java e C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Complessità
| Ciclo | Numero di confronto |
|---|---|
| 1 ° | (n-1) |
| 2 ° | (n-2) |
| 3 ° | (n-3) |
| … | … |
| ultimo | 1 |
Numero di confronti: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2quasi uguale a .n2
Complessità =O(n2)
Inoltre, possiamo analizzare la complessità semplicemente osservando il numero di loop. Ci sono 2 loop quindi la complessità è .n*n = n2
Complessità temporali:
- Complessità del caso peggiore: se vogliamo ordinare in ordine crescente e l'array è in ordine decrescente, si verifica il caso peggiore.
O(n2) - Complessità caso migliore: si verifica quando l'array è già ordinato
O(n2) - Complessità case media: si verifica quando gli elementi dell'array sono in ordine confuso (né ascendente né discendente).
O(n2)
La complessità temporale dell'ordinamento della selezione è la stessa in tutti i casi. Ad ogni passo, devi trovare l'elemento minimo e metterlo al posto giusto. L'elemento minimo non è noto fino a quando non viene raggiunta la fine dell'array.
Complessità spaziale:
La complessità dello spazio è O(1)dovuta al fatto che tempviene utilizzata una variabile aggiuntiva .
Selezione Ordina applicazioni
L'ordinamento di selezione viene utilizzato quando:
- un piccolo elenco deve essere ordinato
- il costo dello scambio non ha importanza
- il controllo di tutti gli elementi è obbligatorio
- il costo della scrittura su una memoria è importante come nella memoria flash (il numero di scritture / scambi è
O(n)rispetto al bubble sort)O(n2)
