Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Selection sort: cos’è e come funziona

Non ha ancora votato nessuno.

L’algoritmo di selection sort è un semplice algoritmo di ordinamento che seleziona ripetutamente l’elemento più piccolo (o più grande, a seconda dell’implementazione) dall’array non ordinato e lo posiziona nella giusta posizione nell’array ordinato.

Il Selection Sort è un algoritmo di ordinamento che funziona trovando il valore massimo (o minimo) e posizionandolo nella giusta posizione, iterando attraverso la lista di elementi. Le due fasi che hai menzionato, “max(A)” e “swap(max(A), A[j])”, rappresentano due passaggi fondamentali all’interno del Selection Sort:

  1. max(A): In questa fase, l’algoritmo cerca il valore massimo all’interno dell’array non ordinato A. Scansiona tutti gli elementi dalla posizione 0 fino a una posizione specifica j (inizialmente, j è l’ultima posizione dell’array, quindi decrementa ad ogni iterazione). Durante questa scansione, tiene traccia del valore massimo trovato finora.
  2. swap(max(A), A[j]): Una volta trovato il valore massimo all’interno dell’array non ordinato A, l’algoritmo esegue uno scambio tra il valore massimo e l’elemento corrispondente alla posizione j. Questo posiziona il valore massimo nella sua posizione corretta all’interno della lista ordinata, ponendo l’elemento più grande (o più piccolo, a seconda dell’implementazione) nell’ultima posizione dell’array ordinato.

Il processo continua con la riduzione di j (il “cursore a ritroso”) per analizzare l’elemento precedente nella lista non ordinata e posizionare il valore massimo successivo (o minimo) nella posizione corretta. Questo procedimento viene ripetuto finché l’intera lista non è ordinata.

In altri termini la fase “max(A)” individua il valore massimo nell’array non ordinato fino a una posizione specifica, mentre la fase “swap(max(A), A[j])” sposta il valore massimo trovato nella sua corretta posizione nell’array ordinato. Iterando attraverso questa procedura per ogni elemento, l’array viene ordinato dall’alto verso il basso (o dal basso verso l’alto, a seconda dell’implementazione).

Esempio pratico di selection sort


Cerchi un hosting economico per il tuo sito o blog? Tophost ti aspetta (clicca qui) - Puoi anche usare il coupon sconto esclusivo 7NSS5HAGD5UC2 per spendere di meno ;-)

Passo 1:

Consideriamo un array iniziale come A=[7,2,9,4,5].

Passo 2:

Si inizia con l’iterazione dell’array per trovare il valore più piccolo. Utilizzeremo una funzione astratta min_index(A, start) che restituisce l’indice dell’elemento più piccolo nell’array A a partire dall’indice ‘start’.

  • min_index(A, 0) restituirà l’indice 1 (valore 2) poiché 2 è il più piccolo nell’array.

Passo 3:

Si effettua lo swap tra l’elemento in posizione 0 (7) e l’elemento più piccolo trovato (2). La funzione swap(a, b) scambia gli elementi nella posizione ‘a’ e ‘b’.

  • Dopo lo swap, l’array diventa A=[2,7,9,4,5].

Passo 4:

Ora si itera sull’array rimanente (escludendo il primo elemento già ordinato).

  • min_index(A, 1) restituirà l’indice 3 (valore 4) poiché 4 è il più piccolo nell’array escludendo il primo elemento.

Passo 5:

Si effettua lo swap tra l’elemento in posizione 1 (7) e l’elemento più piccolo trovato (4).

  • Dopo lo swap, l’array diventa A=[2,4,9,7,5].

Passo 6:

Si procede iterando sull’array rimanente.

  • min_index(A, 2) restituirà l’indice 4 (valore 5) poiché 5 è il più piccolo nell’array escludendo i primi due elementi.

Passo 7:

Si effettua lo swap tra l’elemento in posizione 2 (9) e l’elemento più piccolo trovato (5).

  • Dopo lo swap, l’array diventa A=[2,4,5,7,9].

Passo 8:

L’array è ordinato completamente.

Origine e efficacia dell’algoritmo:

L’algoritmo di selection sort è stato ideato da un informatico chiamato John von Neumann nel 1956. È un algoritmo semplice e intuitivo, ma non è efficiente come alcuni altri algoritmi di ordinamento, specialmente per grandi insiemi di dati. La sua complessità temporale è di O(n^2), dove ‘n’ è la dimensione dell’array. Questo lo rende inefficiente per grandi dataset, ma può essere utile per piccoli set di dati o come punto di partenza per capire i concetti di ordinamento.

Viene spesso studiato come esempio introduttivo di algoritmi di ordinamento poiché è facile da comprendere e implementare, e offre una buona base per capire altri algoritmi più efficienti come il quicksort o il mergesort.

👇 Da non perdere 👇



Questo sito esiste da 4459 giorni (12 anni), e contiene ad oggi 6260 articoli (circa 5.008.000 parole in tutto) e 13 servizi online gratuiti. – Leggi un altro articolo a caso

Ti sembra utile o interessante? Vota e fammelo sapere.

Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.