Ordinamento della selezione è un algoritmo di ordinamento semplice ed efficiente che funziona selezionando ripetutamente l'elemento più piccolo (o più grande) dalla parte non ordinata dell'elenco e spostandolo nella parte ordinata dell'elenco.

L'algoritmo seleziona ripetutamente l'elemento più piccolo (o più grande) dalla parte non ordinata dell'elenco e lo scambia con il primo elemento della parte non ordinata. Questo processo viene ripetuto per la parte rimanente non ordinata finché l'intero elenco non viene ordinato.

Come funziona l'algoritmo di ordinamento della selezione?

Consideriamo come esempio il seguente array: arr[] = {64, 25, 12, 22, 11}

Primo passaggio:

• Per la prima posizione nell'array ordinato, l'intero array viene attraversato in sequenza dall'indice 0 al 4. La prima posizione dove 64 è memorizzato attualmente, dopo aver attraversato l'intero array è chiaro che undici è il valore più basso.
• Pertanto, sostituisci 64 con 11. Dopo un'iterazione undici , che risulta essere il valore più basso nell'array, tende ad apparire nella prima posizione dell'elenco ordinato.

Algoritmo di ordinamento della selezione | Scambia il primo elemento con il minimo nell'array

Secondo passaggio:

• Per la seconda posizione, dove è presente 25, attraversare nuovamente il resto dell'array in modo sequenziale.
• Dopo aver attraversato, lo abbiamo trovato 12 è il secondo valore più basso nell'array e dovrebbe apparire al secondo posto nell'array, quindi scambia questi valori.

Algoritmo di ordinamento della selezione | scambiando i=1 con l'elemento minimo successivo

Terzo passaggio:

• Ora, per il terzo posto, dove 25 è nuovamente presente, attraversa il resto dell'array e trova il terzultimo valore presente nell'array.
• Durante il transito, 22 è risultato essere il terzultimo valore e dovrebbe apparire al terzo posto nell'array, quindi scambia 22 con elemento presente in terza posizione.

Algoritmo di ordinamento della selezione | scambiando i=2 con l'elemento minimo successivo

Quarto passaggio:

• Allo stesso modo, per la quarta posizione attraversa il resto dell'array e trova il quarto elemento più piccolo nell'array
• COME 25 è il quarto valore più basso, quindi si posizionerà alla quarta posizione.

Algoritmo di ordinamento della selezione | scambiando i=3 con l'elemento minimo successivo

Quinto passaggio:

• Alla fine il valore più grande presente nell'array viene automaticamente posizionato nell'ultima posizione dell'array
• L'array risultante è l'array ordinato.

Algoritmo di ordinamento della selezione | Array ordinato obbligatorio

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

// C++ program for implementation of // selection sort #include  using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of  // unsorted subarray  for (i = 0; i < n - 1; i++) {  // Find the minimum element in  // unsorted array  min_idx = i;  for (j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx])  min_idx = j;  }  // Swap the found minimum element  // with the first element  if (min_idx != i)  swap(arr[min_idx], arr[i]);  } } // Function to print an array void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++) {  cout << arr[i] << ' ';  cout << endl;  } } // Driver program int main() {  int arr[] = { 64, 25, 12, 22, 11 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  selectionSort(arr, n);  cout << 'Sorted array: 
';  printArray(arr, n);  return 0; } // This is code is contributed by rathbhupendra>

// C program for implementation of selection sort #include  void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of unsorted subarray  for (i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  min_idx = i;  for (j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first element  if(min_idx != i)  swap(&arr[min_idx], &arr[i]);  } } /* Function to print an array */ void printArray(int arr[], int size) {  int i;  for (i=0; i < size; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver program to test above functions int main() {  int arr[] = {64, 25, 12, 22, 11};  int n = sizeof(arr)/sizeof(arr[0]);  selectionSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>

// Java program for implementation of Selection Sort import java.io.*; public class SelectionSort {  void sort(int arr[])  {  int n = arr.length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  void printArray(int arr[])  {  int n = arr.length;  for (int i=0; i

# Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining  # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Scambia l'elemento minimo trovato con # il primo elemento A[i], A[min_idx] = A[min_idx], A[i] # Codice driver da testare sopra print ('Array ordinato ') for i in range(len(A)): print(A[i],end=' ')>

// C# program for implementation  // of Selection Sort using System; class GFG {   static void sort(int []arr)  {  int n = arr.Length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n - 1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i + 1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  static void printArray(int []arr)  {  int n = arr.Length;  for (int i=0; i

>

 // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$basso]) { $tmp = $arr[$i]; $arr[$i] = $arr[$basso]; $arr[$basso] = $tmp; } } } // Codice driver $arr = array(64, 25, 12, 22, 11); $len = conteggio($arr); selezione_sort($arr, $len); echo 'Array ordinato: 
'; per ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Analisi della complessità dell'ordinamento della selezione

Complessità temporale: La complessità temporale dell'ordinamento della selezione è SU ² ) poiché ci sono due cicli nidificati:

• Un ciclo per selezionare un elemento di Array uno per uno = O(N)
• Un altro ciclo per confrontare quell'elemento con ogni altro elemento dell'array = O(N)
• Pertanto complessità complessiva = O(N) * O(N) = O(N*N) = O(N²)

Spazio ausiliario: O(1) poiché l'unica memoria aggiuntiva utilizzata è per variabili temporanee durante lo scambio di due valori in Array. L'ordinamento di selezione non effettua mai più di O(N) scambi e può essere utile quando la scrittura in memoria è costosa.

età di rihanna

Vantaggi dell'algoritmo di ordinamento della selezione

• Semplice e facile da capire.
• Funziona bene con set di dati di piccole dimensioni.

Svantaggi dell'algoritmo di ordinamento della selezione

• L'ordinamento della selezione ha una complessità temporale di O(n^2) nel caso peggiore e medio.
• Non funziona bene su set di dati di grandi dimensioni.
• Non preserva l'ordine relativo degli elementi con chiavi uguali, il che significa che non è stabile.

Domande frequenti sull'ordinamento della selezione

Q1. L'algoritmo di ordinamento della selezione è stabile?

L'implementazione predefinita dell'algoritmo di ordinamento della selezione è non stabile . Tuttavia, può essere reso stabile. Si prega di consultare il Ordinamento di selezione stabile per dettagli.

Q2. L'algoritmo di ordinamento della selezione è attivo?

Sì, l'algoritmo di ordinamento della selezione è un algoritmo sul posto, poiché non richiede spazio aggiuntivo.