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 Fusao. Complexidade: O(n log n)
005// Exemplo de metodo no paradgma "DIVISAO e CONQUISTA"
006// Invocar: #include "ordena_fusao.h"
007//          ...
008//          XbibliotecaLOBx__ordenaMetadesFusao(int V[], int esq, int dir)
009
010// Ordena por Fusao (Merge Sort)
011// Programa recursivo para ordenar uma lista de inteiros usando a ideia ordenar 2 metades e depois fundi-las.
012
013#define MAX       25000 // maximo de elementos (TAMINI + NTESTES * PASSO) - veja em 'ordena_compara_metodos.c'
014
015// Se V[esq]<=V[esq+1]<=...<=V[med] e V[med+1]<=V[med+2]<=...<=V[dir]
016// Entao funde em ordem unica V[esq] <= V[esq+1] <= ... <= V[dir-1] <= V[dir]
017void XbibliotecaLOBx__Fusao (int V[], int esq, int med, int dir) {
018  int Aux[MAX], i, j, k, e1, d1, e2, d2; // dir=e2
019  e1 = esq;   d1 = med;
020  e2 = med+1; d2 = dir;
021  k = i = e1;
022  j = e2;
023  while (i<=d1 && j<=d2) { // compara os "topos", retire o menor dos dois colocando em nova pilha
024    if (V[i]<V[j]) // "topo" da pilha 1 e' o menor
025      Aux[k++] = V[i++];
026    else
027    if (V[i]>V[j]) // "topo" da pilha 2 e' o menor
028      Aux[k++] = V[j++];
029    else { // havendo empate pegue os dois "topos"
030      Aux[k++] = V[i++];
031      Aux[k++] = V[j++];
032      }
033    }
034  while (i<=d1) // copia restante de V[e1..d1]
035    Aux[k++] = V[i++];
036  while (j<=d2)  // copia restante de V[e2..d2]
037    Aux[k++] = V[j++];
038  for (i=e1; i<=d2; i++) // reconstroi V[e1..d2] ordenado
039    V[i]=Aux[i];
040  }
041
042// Ordena V[esq .. dir] usando tecnica de DIVISAO E CONQUISTA, divida em 2 metades
043// ordene cada uma e depois funda para obter ordem das 2 partes
044void XbibliotecaLOBx__ordenaMetadesFusao (int V[], int esq, int dir) {
045  int med;
046  med = (esq+dir)/2;
047  if (esq<med)
048    XbibliotecaLOBx__ordenaMetadesFusao(V, esq, med);   // ordena V[esq .. m]
049  if (med<dir)
050    XbibliotecaLOBx__ordenaMetadesFusao(V, med+1, dir); // ordena V[m+1 .. dir]
051  XbibliotecaLOBx__Fusao(V, esq, med, dir); // funde em ordem unica V[esq .. m] com V[m+1 .. dir]
052  }