Algoritmi di ordinamento
Data una sequenza di elementi, il nostro obiettivo è quello di ordinarli in modo crescente o decrescente.
La sequenza che prendiamo in considerazione è di tipo numerico ed, in particolare, di tipo intero e si prenderà in considerazione l’ordinamento di tipo crescente.
Chiaramente nulla cambia per l’ordinamento decrescente basterà solamente cambiare qualche segno di comparazione.
Iniziamo subito con il primo degli algoritmi
Bubble sort
Il bubble sort è il più semplice algoritmo di ordinamento non molto efficiente.
Difatti, si utilizza per introdurre gli sviluppatori agli algoritmi ed alla complessità computazionale.
L’algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati: quelli più piccoli “risalgono” verso un’estremità della lista, mentre quelli più grandi “affondano” verso l’estremità opposta, come le bolle in un bicchiere di spumante.
Ad ogni iterazione, si considerano, una ad una, tutte le possibili coppie di elementi adiacenti, scambiandoli se risultano nell’ordine errato. Dopo ogni iterazione, l’elemento massimo sarà in fondo alla sequenza.
Selection Sort
Il selection sort o ordinamento per selezione, opera dividendo la sequenza di input in due parti: la sottosequenza di elementi già ordinati (che occupa le prime posizioni dell’array) e la sottosequenza di elementi non ordinati (che occupa il resto dell’array).
Inizialmente, la sottosequenza ordinata è vuota, mentre quella non ordinata rappresenta l’intero input.
L’algoritmo seleziona di volta in volta il numero minore nella sottosequenza non ordinata e lo sposta in quella ordinata.
Insertion Sort
L’insertion sort è più efficiente di algoritmi come il selection sort o il bubble sort. È molto efficiente per l’ordinamento di array di dimensione molto piccola o per array parzialmente ordinati.
L’idea di ordinamento è simile al modo in cui un giocatore di Burraco ordina le carte.
Si inizia con la mano vuota e le carte capovolte sul tavolo, poi si prende una carta alla volta dal tavolo e la si inserisce nella giusta posizione. Per trovare la giusta posizione per una carta, la si confronta con le altre carte nella mano, da destra verso sinistra.
Ogni carta più grande verrà spostata verso destra in modo da fare posto alla carta da inserire.
BIBLIOGRAFIA
https://it.wikiversity.org/wiki/Il_problema_dell%27ordinamento
https://en.wikipedia.org/wiki/Bubble_sort
https://en.wikipedia.org/wiki/Insertion_sort
