Implementazioni di algoritmi/Insertion sort: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
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)