ALGORITMO MERGESORT

Ainda existe uma discussão sobre o assunto, mas apareceram evidências de que o algoritmo mergesort foi proposto por John Von Neumann em 1945. Essa discussão existe, pois estudar as várias contribuições que ele fez é, ao mesmo tempo, complexa e fascinante. Essa complexidade devesse em parte a existência de muitas fontes de informação, algumas pouco acessíveis, outras discordantes entre si ou polêmicas. A atribuição a ele veio de Knuth, que argumentou no seu livro ‘Arte de Programação Computacional: Ordenando e Procurando’ que Von Neumann foi o primeiro a descrever a idéia.

GIACON, André P., et al. MERGESORT. Faculdade de Tecnologia - Unicamp, 2010

void mergesort(int *vet,int inicio,int fim){     

     if(inicio == fim ) { return; }     

     int meio = (inicio + fim )/2;     

     mergesort(vet, inicio, meio );

     mergesort(vet, meio + 1, fim);

     int k = 0;

     int i = inicio;

     int j = meio + 1;

     //A linha abaixo cria um novo vetor auxiliar

     int *vetaux = (int *) malloc(sizeof (int) * (fim-inicio+1));     

     while( i < meio + 1 || j < fim + 1 ) {

           if( i == meio + 1 ) {

               vetaux[k] = vet[j];

               j++;

               k++;

           }else{

                 if ( j == fim + 1 ) {

                      vetaux[k] = vet[i];

                      i++;

                      k++;

                 }else{

                       if( vet[i] < vet[j] ) {

                           vetaux[k] = vet[i];

                           i++;

                           k++;

                       }else{

                             vetaux[k] = vet[j];

                             j++;

                             k++;

                       }

                 }

           }

     }

     //Este laco copia o vetor auxiliar no vetor principal

     for( i = inicio; i <= fim; i++ ){

          vet[i] = vetaux[i - inicio];

     }

}

ADEUS STEVE... E MUITO OBRIGADO!

Digito este texto em meu computador pessoal, pequeno, leve e poderoso, para homenagear o homem que tornou possível a existência deste equipamento aqui, na minha frente, fazendo parte da minha vida. Desde já, obrigado, Steve Jobs.

Nunca tive um computador Apple; nunca usei um sistema Apple; sempre vivi rodeado de IBM-PC's, DOS, Windows e outros mais. Mas, mesmo sem ter feito parte dos produtos criados por este humano ímpar, sei reconhecer que foi apenas por causa de Jobs que tenho o privilégio de viver um período da história deste planeta repleto de tecnologia ao alcance das pessoas comuns.

Este foi o sonho de Jobs, sonho renegado pelos grandes de sua época, mas que não o abalaram em sua visão: pessoas comuns podem ter computadores. Desde que as coisas ficaram sérias na minha vida, foi o meu trabalho com computadores que me manteve erguido. Tudo o que eu sou hoje, tudo o que eu tenho, tudo o que eu construí, só foi possível porque Steve Jobs não desistiu. Sem ele, provavelmente apenas os meus netos teriam computadores iguais aos que eu posso ter hoje.

Steve Jobs foi um daqueles humanos iluminados, que a partir de agora ganha a eternidade pelo trabalho que fez permanecer. Podem passar décadas, séculos, pode a tecnologia evoluir para além da mais ousada ficção científica, ainda assim a marca da maçã jamais será esquecida. Jobs não morreu... Jobs foi para as nuvens!

ALGORITMO HEAPSORT PARA O 4º PERÍODO DE SISTEMAS

Um heap é uma estrutura de dados organizada como árvore binária. Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.


void heapsort( vetor, elementos ) {    
     int i = n / 2;
     int t, pai, filho, inf, j;
     inf=1;
     while(inf){        
          if( i > 0 ) {
              i--;
              t = vet[i];            
          }else{
              n--;
              if ( n == 0 ) { return; }
              t = vet[n];              
              vet[n] = *vet;              
          }        
          pai = i;
          filho = 2 * pai + 1;                  
          while(filho<n) {                
                 if(filho+1<n && vet[filho+1]>vet[filho]){                                
                     filho++;
                 }                
                 if( vet[filho] > t ) {
                     vet[pai] = vet[filho];
                     pai = filho;
                     filho = 2 * pai + 1;
                 }else{
                       break;
                 }
          }        
          vet[pai] = t;        
     }
}