Root: Ordenação por Inserção moved to Ordenação por Inserção

2008-11-12T09:04:17Z

Ordenação por Inserção moved to Ordenação por Inserção

← Older revision	Revision as of 09:04, 12 November 2008
(No difference)

Root at 13:44, 19 May 2005

2005-05-19T13:44:34Z

New page

== 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;
}

Ordenação por Inserção - Revision history

Root: Ordenação por Inserção moved to Ordenação por Inserção

Root at 13:44, 19 May 2005