ALGORITMI ALGORITMI DI DI

ORDINAMENTOORDINAMENTO

INSERTIONINSERTIONSORTSORT

IDEA DI BASE: collocare uno dopo l’altro tutti gli elementi ai dell’insieme nella posizione corretta del sottoinsieme già ordinato costituito dagli elementi a1, a2, . . . , ai-1, inserendolo facendo scorrere a destra gli elementi maggiori.

INSERTIONSORTINSERTIONSORT

Algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria. Pur essendo molto meno efficiente di algoritmi più avanzati, può avere alcuni vantaggi: •ad esempio, è semplice da implementare ed è efficiente per insiemi di partenza che sono quasi ordinati.

DESCRIZIONE DELL’ALGORITMO

•L'algoritmo solitamente ordina la sequenza sul posto. •Si assume che la sequenza da ordinare sia partizionata in una sottosequenza già ordinata, all'inizio composta da un solo elemento, e una ancora da ordinare. •Alla k-esima iterazione, la sequenza già ordinata contiene k elementi. In ogni iterazione, viene rimosso un elemento dalla sottosequenza non ordinata (scelto, in generale, arbitrariamente) e INSERITO (da cui il nome dell'algoritmo) nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.

INSERTIONSORTINSERTIONSORT

DESCRIZIONE DELL’ALGORITMO

Un'implementazione tipica dell'algoritmo utilizza due indici:•uno punta all'elemento da ordinare (ad es. d).•l'altro all'elemento immediatamente precedente (d-1). Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito. Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

INSERTIONSORTINSERTIONSORT

ESEMPIO DI FUNZIONAMENTO

Di seguito sono mostrati i passi compiuti dall'algoritmo per ordinare la sequenza [6, 5, 3, 1, 8, 7, 2, 4]. In ogni passo, l'elemento sottolineato è quello considerato, mentre quello in grassetto è l'elemento spostato nel passo precedente.

INSERTIONSORTINSERTIONSORT

PSEUDOCODICE

/* InsertionSort ordine crescente */ #include <stdio.h>#include <stdlib.h> int main(){ int n, a[1000], i, d, t; /* * Legge in input il numero n ed n numeri interi che memorizza nell'array. */  printf("Inserisci il numero di elementi da ordinare\n"); scanf("%d", &n); printf("Inserisci %d numeri interi\n", n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } /* * Ordina l’array. * Si ricorda che i = 1 fa riferimento al secondo elemento dell’array */ for (i = 1; i < n; i++) { d = i; while ( d > 0 && a[d] < a[d-1])

{ t = a[d]; a[d] = a[d-1]; a[d-1] = t; d--; } } /* * Restituisce l’array ordinato. */  printf("Lista ordinata in ordine crescente:\n"); for (i = 0; i < n; i++) { printf("%d\n", a[i]); } system("pause"); return 0;}

INSERTIONSOINSERTIONSORTRT