Implementazioni di algoritmi/Insertion sort: differenze tra le versioni
Aggiunto pseudocodice |
|||
Riga 9: | Riga 9: | ||
insertion_sort(x[], n) |
insertion_sort(x[], n) |
||
for i ← 1 to n do |
for i ← 1 to n - 1 do |
||
app ← x[i] |
app ← x[i] |
||
j ← i - 1 |
j ← i - 1 |
Versione delle 09:14, 18 apr 2007
L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.
Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. L'algoritmo utilizza due indici: il primo punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il primo indice avanza di una posizione e il secondo indice riparte dall'elemento precedente quello puntato dal primo. Se l'elemento puntato dal secondo indice non è maggiore di quello a cui punta il primo indice, il secondo indice avanza; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere inserito (da qui insertion). L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.
Un algoritmo simile all'Insertion Sort ma contenente un miglioramento significativo è lo Shell sort.
Pseudocodice
insertion_sort(x[], n) for i ← 1 to n - 1 do app ← x[i] j ← i - 1 while (j >= 0) and (x[j] > app) do x[j + 1] ← x[j] j ← j - 1 x[j + 1] ← app
Implementazioni
Seguono alcuni esempi di implementazione in vari linguaggi di programmazione.
C
void insertion_sort(int x[], int n) { int i, j, app; for (i=1; i<n; i++) { app = x[i]; j = i-1; while ((j>=0) && (x[j]>app)) { x[j+1] = x[j]; j--; } x[j+1] = app; } }
La funzione qui riportata riceve due parametri: x è l'array da ordinare, n è il numero dei suoi elementi.
Java
public static void insertionsort(int[]v, int in, int fin) throws Exception{ if(in<0||fin>(v.length-1)||in>=fin) throw new Exception("Indici Errati"); for(int i=in+1;i<=fin;i++){ for(int j=in;j<i;j++){ if(v[i]<v[j])scambia(v,i,j); }//for interno }//for esterno } protected static void scambia(int[]v, int a, int b){ int tmp = v[a]; v[a]=v[b]; v[b]=tmp; System.out.println("Invertiti "+v[a]+" e "+v[b]); }
Python
def insertionsort(array): for removed_index in range(1, len(array)): removed_value = array[removed_index] insert_index = removed_index while insert_index > 0 and array[insert_index - 1] > removed_value: array[insert_index] = array[insert_index - 1] insert_index = insert_index - 1 array[insert_index] = removed_value
FORTRAN
SUBROUTINE SSORT (X, IY, N, KFLAG) IMPLICIT NONE DO 100 I=2,N IF ( X(I).GT.X(I-1) ) THEN DO 50 J=I-2,1,-1 IF(X(I).LT.X(J)) go to 70 50 CONTINUE J=0 70 TEMP=X(I) ITEMP=IY(I) DO 90 K=I,J+2,-1 IY(K)=IY(K-1) 90 X(K)=X(K-1) X(J+1)=TEMP IY(J+1)=ITEMP ENDIF 100 CONTINUE RETURN END
Lisp
(define insert (lambda (n l) (cond ((null? l) (list n)) (else (if (< n (car l)) (cons n l) (cons (car l) (insert n (cdr l)))))))
Pseudocodice per linguaggi funzionali
insert :: Ord a => a -> [a] -> [a] insert item [] = [item] insert item (h:t) | item <= h = item:h:t | otherwise = h:(insert item t) insertsort :: Ord a => [a] -> [a] insertsort [] = [] insertsort (h:t) = insert h (insertsort t)