Ordenação por Inserção

Ordenação de Vectores

Exemplo de preenchimento.

 void init() {
   int i;
   vect = (int *)malloc(N * sizeof(int));
   for (i=0; i < N; i++)
     vect[i] =  rand() % M;
 }

Implementação do algoritmo.

 void isort() {
   int i, j;
   for (i=1; i < N; i++) {
     int key = vect[i];
     j = i-1;
     while (j >= 0 && vect[j] > key) {
       vect[j+1] = vect[j];
       j--;
     }
     vect[j+1] = key;
   }
 }

Ordenação de Listas Simplesmente Ligadas

Apresentam-se duas versões do algoritmo de ordenação por inserção para listas simplesmente ligadas: com e sem sentinela.

Sem sentinela

 void isort() {
   link pa, pb, px, py, pz;
 
   for (px = head->next, py = head; px != NULL; px = pz) {
     py->next = px->next;
     pz = px->next;
 
     for (pb=head, pa=pb; pb!=pz; pa=pb, pb=pb->next) {
       if (pb->item > px->item)
         break;
     }
     if (pa == pb) { head = px; }
     else          { pa->next = px; }
     px->next = pb;
     if (pb == pz) { py = px; }
   }
 }

Com Sentinela

Criação e inicialização da lista.

 void init() {
   int i;
   link t, u, a;
   heada = (link)malloc(sizeof *heada);
   headb = (link)malloc(sizeof *headb);
   a = heada;
   for (i = 0, t = a; i < N; i++) {
     t->next = malloc(sizeof *t); 
     t = t->next; t->next = NULL;
     t->item = rand() % M; 
   }
 }

Algoritmo de ordenação.

 void isort() {
   link t, u, x, b;
 
   b = headb; b->next = NULL;
   for (t = heada->next; t != NULL; t = u) {
     u = t->next;
     for (x = b; x->next != NULL; x = x->next)
       if (x->next->item > t->item) break;
     t->next = x->next; x->next = t; 
   }
   heada->next = headb->next;
   headb->next = NULL;
 }