Struttura dei dati e ordinamento di selezione degli algoritmi

L'ordinamento della selezione è un semplice algoritmo di ordinamento. Questo algoritmo di ordinamento è un algoritmo basato sul confronto sul posto in cui l'elenco è diviso in due parti, la parte ordinata all'estremità sinistra e la parte non ordinata all'estremità destra. Inizialmente, la parte ordinata è vuota e la parte non ordinata è l'intero elenco.

L'elemento più piccolo viene selezionato dall'array non ordinato e scambiato con l'elemento più a sinistra, e quell'elemento diventa una parte dell'array ordinato. Questo processo continua a spostare il limite dell'array non ordinato di un elemento a destra.

Questo algoritmo non è adatto per grandi insiemi di dati in quanto la sua complessità media e nel caso peggiore sono di Ο (n ² ), doven è il numero di elementi.

Come funziona l'ordinamento della selezione?

Considera il seguente array raffigurato come esempio.

Per la prima posizione nell'elenco ordinato, l'intero elenco viene scansionato in sequenza. La prima posizione in cui è attualmente memorizzato 14, cerchiamo in tutta la lista e troviamo che 10 è il valore più basso.

Quindi sostituiamo 14 con 10. Dopo un'iterazione, 10, che sembra essere il valore minimo nell'elenco, appare nella prima posizione dell'elenco ordinato.

Per la seconda posizione, dove risiede 33, iniziamo a scansionare il resto della lista in modo lineare.

Troviamo che 14 è il secondo valore più basso nell'elenco e dovrebbe apparire al secondo posto. Scambiamo questi valori.

Dopo due iterazioni, due valori minimi vengono posizionati all'inizio in modo ordinato.

Lo stesso processo viene applicato al resto degli elementi nell'array.

Di seguito è una rappresentazione pittorica dell'intero processo di smistamento:

Ora, impariamo alcuni aspetti di programmazione dell'ordinamento di selezione.

Algoritmo

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Pseudocodice

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Per conoscere l'implementazione dell'ordinamento di selezione nel linguaggio di programmazione C, fare clic qui .