Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/08/23
003
004// Biblioteca para: ordenar vetor de inteiros via metodo da Propriedade de Monte. Complexidade: O(n log n)
005// Exemplo de metodo no paradgma "DIVISAO e CONQUISTA"
006// Invocar: #include "ordena_monte.h"
007//          ...
008//          XbibliotecaLOBx__ordenaMonte(int V[], int n);
009
010// Ordena vetor de inteiros via metodo da Ordenacao por Propriedade de Monte. Complexidade: O(n log)
011// Propriedade de Monte ("Heap Sort"):
012//   para cada no de uma arvore, a informacao nele e' maior ou igual a de seus filhos
013//   info(no) >= max{ info(no.esq), info(no.dir) }
014// Usa um vetor para a arvore: para um no na posicao i do vetor, seus filhos estao nas posicoes V[2*i+1] e V[2*i+2]
015// Observacao importante: se uma arvore e' o Monte, entao o maior elemento esta na primeira posicao, ou seja,
016//   V[0] >= V[i], para todo i
017// Programa recursivo para ordenar uma lista de inteiros usando a ideia manter propriedade de Monte e separa o maior.
018
019// Macro para trocar par de valores
020#define XbibliotecaLOBx__troquePar(V, IA, IB) {int aux = V[IA]; V[IA] = V[IB]; V[IB] = aux;}
021
022// Supondo que V[] tem a propriedade de Monte exceto talvez em V[k]
023// Entao "desca" o V[k] trocando-o com o maior filho ate' que fique maior que os 2 filhos
024// Neste momento a propriedade de Monte estara restaurada
025void XbibliotecaLOBx__desceElementoMonte (int V[], int k, int N) {
026  int j;
027  while (2*k + 1 < N) { // tem algum filho?  (V[k] -> { V[2*k, V[2*k+2] }
028    j = 2*k + 1; // primeiro filho de "k"
029    if (j < N-1 && V[j] < V[j+1]) // se tem 2 filhos e maior em j+1, aponte para j+1
030      j++;
031    if (V[k] >= V[j]) {
032       break;
033       }
034    XbibliotecaLOBx__troquePar(V, k, j); // o "define" acima colocara aquele codigo aqui
035    k = j; // recome com o "maior filho"
036    }
037  }
038
039void XbibliotecaLOBx__ordenaMonte (int V[], int tam) {
040  int k, N = tam;
041  // Cria propriedade inicial de Monte
042  for (k = N/2-1; k >= 0; k--) // comece pelo primeiro no que tem filho
043    XbibliotecaLOBx__desceElementoMonte(V, k, N); // desca-o de modo sua sub-arvore ser Monte
044  while (N > 0) {
045    // Elemento no topo e' maior => passe para ultima posicao
046    XbibliotecaLOBx__troquePar(V, 0, N-1);
047    // Estragou propriedade de monte na posicao 0, desca para recuperar propriedade
048    XbibliotecaLOBx__desceElementoMonte(V, 0, --N);
049    }
050  }