Come programmare: gli algoritmi selection sort, quick sort, bubble sort

Naviga SWZ: Home Page » Tech
News del 01 Dicembre 16 Autore: Fabio Ferraro
Esistono vari metodi per ordinare un insieme di elementi nel mondo della programmazione.

Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 1

Oggi analizzeremo la logica utilizzata negli algoritmi selection sort, quick sort, bubble sort. Ovviamente ognuno di questi algoritmi genera lo stesso risultato finale ma con
un ´efficienza diversa.

Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 2

Gli algoritmi selection sort e bubble sort sono semplici ma non particolarmente efficienti. I tipi di algoritmi che analizzeremo sono molto usati nelle strutture dati Vettoriali.

Selection sort

Il primo passo consiste nel trovare nella sequenza di elementi l’elemento minore e scambiarlo con l´elemento nella posizione iniziale della sequenza. Da questo momento si opererà come se avessimo due sotto-sequenze (una ordinata e una non). 

Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 3
Successivamente si va a cercare il valore minimo nella sequenza non ordinata e lo si porta sull´ultima posizione della sequenza ordinata. Sull´insieme degli elementi non ordinato si ripeterà la stessa operazione fino a quanto non conterrà un solo elemento (che sarà ordinato e sarà il valore max). Il codice per rappresentare questa soluzione è il seguente.

Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 4

Bubble sort

Con questo metodo l´ordinamento della sequenza di elementi avverrà confrontando gli elementi a coppie ed effettuando lo scambio se si verifica la seguente condizione.

                                           elemento (2) < elemento (1)


Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 5

Il processo si ripeterà fino all´assenza di scambi. A questo punto avremo la sequenza ordinata.
Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 6
Quick sort

Il quick sort è più complesso ma decisamente più efficiente eseguendo un numero minore di scansioni degli elementi, risulta essere il più veloce algoritmo di ordinamento “general purpose”.

Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 7
Si parte scegliendo un elemento, detto pivot inserendo a sinistra e a destra gli elementi secondo il pivot ordinandoli ricorsivamente. La ricorsione termina quando si deve ordinare un array di un solo elemento.


Come programmare: gli algoritmi selection sort, quick sort, bubble sort - immagine 8
Molto sconveniente risulta selezionare come pivot il primo elemento della sequenza
La scansione, incontrato un elemento uguale al pivot, si fermerà.

Esistono tanti algoritmi per ordinare sequenze di elementi, vi invitiamo ad approfondire l´argomento per migliorare, tramite la loro logica anche nell´ordine degli scaffali o altro, associando ad ognuno di loro un numero/codice.

La Community di SWZone.it

La community con le risposte che cerchi ! Partecipa é gratis !
Iscrizione ForumIscriviti al Forum

Newsletter

Vuoi ricevere tutti gli aggiornamenti di SWZone direttamente via mail ?
Iscrizione NewsletterIscriviti alla Newsletter

NOTIZIE CORRELATE