/* ======================================================================== Name : teste.c Author : Marco Aurelio Version : Copyright : On Eclipse Indigo - Ubuntu 10.04 Description : Ordenacao internaAtualizado.... ======================================================================== */#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define N 20typedef int tchave;typedef char tinfo[20];typedef struct Cel{ tchave chave; tinfo info; }celula;typedef celula vetor[N];void inicializar() { int i; vetor v; srand(time(NULL)); for(i=0;i<N;i++) { v[i].chave = (rand()%100); } }void troca(int *a, int *b){ int temp; temp=*a; *a=*b; *b=temp;}//==============================================================================void booble(vetor lista){int passada, i, trocou; for(passada = 1; passada < N; passada++) { trocou = 0; for(i = 0; i < N-passada; i++) if(lista[i].chave > lista[i+1].chave) { troca(&lista[i], &lista[i+1]); trocou = 1; } if(trocou == 0) break; }}//=============================================================================void selects(vetor lista){ int i, j, min; for (i = 0; i < N; i++) { min = i; for (j = i+1; j < N; j++) if (lista[j].chave < lista[min].chave) min = j; troca(&lista[min], &lista[i]); }}//==============================================================================void quick(vetor lista, int min, int max){ int i = min; int j = max; tchave pivo = lista[min].chave; do { while(lista[i].chave < pivo && i < max) i++;//verifica se o item na posicao "i" e menor que o "pivo" e se "i" e menor que a ultima posicao "max" while(lista[j].chave > pivo && j > min) j--;//verifica se o item na posicao "j" e maior que o "pivo" e se "j" e maior que a primeira posicao "min" if(i <= j) // se "i" for menor ou igual a "j" { troca(&lista[i], &lista[j]); i++; j--;//efetua a troca do item na posicao "i" } } while(i <= j); if(min < j) quick(lista, min, j); if(max > i) quick(lista, i, max);}//=============================================================================void shell(vetor v, int unit)// unit e um parametro que informa em quantas partes o vetor sera dividido{ long int i, j; celula temp; int k; k=1; do { k = unit * k + 1; } while(k < N); do { k /= unit; for(i = k; i < N; i++) { temp = v[i]; j = i-k; while(j >= 0 && temp.chave < v[j].chave) { v[j+k] = v[j]; j -= k; } v[j+k] = temp; } }while(k > 1);}//=============================================================================void merge(vetor v, int tam)//tam e um parametro que informa o tamanho do vetor{ int meio; if(tam > 1) { meio = tam/2; merge(v, meio); merge(v+meio, tam-meio); pass(v, tam); }}//=============================================================================void insert(vetor v){ int i, j; celula temp; for(i = 1; i < N; i++) { temp = v[i]; j = i-1; while(j >= 0 && temp.chave < v[j].chave) { v[j+1] = v[j]; j--; } v[j+1] = temp; }}//=============================================================================void heap(vetor v, int n)//n e um parametro que informa o tamanho do vetor{ int i; // construindo o heap for( i = (n-1 / 2); i >=1 ; i--){ ajusta(v, i, n); } // excluindo a raiz e atualizando o heap for( i = n-1; i >=1; i--){ troca(&v[i+1], &v[1]); ajusta(v, 1, i); }}//=============================================================================void ajusta(vetor v, int i,int n){ long int j; tchave chave; celula raiz; int fim; fim =0; raiz = v[i]; chave = v[i].chave; j = 2 * i; //raiz recebe o registro na posicao "i" e a chave recebe o valor da chave no registro "i" // j recebe duas vezes o