Implementazioni di algoritmi/Insertion sort: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
Riga 1: Riga 1:
L''''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[algoritmo]] relativamente semplice per ordinare un [[array]]. Esso è un [[Algoritmo in loco|algoritmo ''in place'']], cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.
L''''Insertion sort''', in italiano '''ordinamento a inserimento''', è un [[algoritmo]] relativamente semplice per ordinare un [[array]]. Esso è un [[Algoritmo in loco|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 sempre dal primo elemento. Se il primo elemento 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'').
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.
L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.



Versione delle 21:51, 3 gen 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.

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)