Insertion sort

Algoritmo alternativo al bubble sort ma più complesso…

A ogni passata l’elemento i-esimo viene parcheggiato in X.
Gli elementi più grandi, che lo precedono, vengono spostati in avanti di una posizione e X viene posizionato al posto giusto.
In questo modo il sottovettore da 1 a i è sicuramente ordinato.

Procedure INSERTSORT(var V: Vettore; N: Integer);
Var
   i, j: Integer;
   X   : Real;
Begin
   For i:=2 To N Do
      Begin
         X:=V[i];
         j:=i-1;
         While(j > 0) And (V[j] > X) Do
            Begin
               V[j+1]:=V[j];
               j:=j-1;
            End;
         V[j+1]:=X;
      End;
End;

Osserva…