View source for 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|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;
  }