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; } }
Apresentam-se duas versões do algoritmo de ordenação por inserção para listas simplesmente ligadas: com e 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; } } }
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; }