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 Ordenacao Rapida. Complexidade: em media O(n log n)
005// Exemplo de metodo no paradgma "DIVISAO e CONQUISTA"
006// Invocar: #include "ordena_insercao.h"
007//          ...
008//          XbibliotecaLOBx__ordenaRapido(int V[], int esq, int dir)
009
010// Programa recursivo para ordenar uma lista de inteiros usando a ideia separar menores e maiores que x
011// depois ordenar cada trecho (se cada trecho for proximo de metade, resulta O(n log n)).
012
013// Ordena Rapido (Quick Sort)
014void XbibliotecaLOBx__ordenaRapido (int V[], int esq, int dir) {
015  int i,j,x,w;
016
017  // Particiona: separa menores que x para esquerda e maiores para direita
018  i = esq;
019  j = dir;
020  x = V[esq]; // x <- qualquer valor entre V[esq] e V[dir]
021  do { // Invariante: max{V[esq],...,V[i-1]  } <= x <= min{V[j+1],...,V[dir]  }
022    while ( V[i] < x ) i++;
023    while ( x < V[j] ) j--;
024    if (i<=j) {
025      if (i<j) {
026        w    = V[i];
027        V[i] = V[j];
028        V[j] = w;
029        }
030      i++;
031      j--;
032      }
033  } while (i<j); // max{V[esq],...,V[j]  } <= x <= min{V[i],...,V[dir]  }
034
035  if (esq<j)
036    XbibliotecaLOBx__ordenaRapido(V, esq, j); // ordena parte esquerda
037  if (i<dir)
038    XbibliotecaLOBx__ordenaRapido(V, i, dir); // ordena parte direita
039  }