/*******************************************************
   - implementação de alguns algoritmos de ordenação 
   - comparação dos algoritmos
   Adaptados de 'Sedgewick, Algorithms in C, 3a. ed' 
*******************************************************/

/******************************************************
   definições auxiliares usadas nos algoritmos
******************************************************/
#include <stdio.h>
#include <stdlib.h>
#define key(A) (A)
#define less(A, B) strLess(A,B)
#define exch(A, B) { Item t = A; A = B; B = t; exchCount++; } 
#define copy(A, B) { A = B; copyCount++; }
#define compexch(A, B) if (less(B, A)) exch(A, B)

#define true  1
#define false 0

typedef char *Item;

/***** contadores das operações ********/
int compCount = 0;
int chCompCount = 0;
int exchCount  = 0;
int copyCount  = 0;

/***** (re)inicialização dos contadores *****/
void resetCounters(){ 
  compCount = 0; 
  chCompCount = 0; 
  exchCount = 0;
  copyCount = 0;
}
    
/****    comparaçãdo de strings    ****/
/****  e contagem das comparações  ****/
int strLess(char *a, char*b){
  int i = 0;
  compCount++;
  for(;;){
    chCompCount++;
    if(a[i] == '\0')  return (b[i] != '\0');
    if(b[i] == '\0')  return false;
    if(a[i] < b[i])     return true;
    if(a[i++] > b[i++]) return false;
  }    
}    

/**** gera um string aleatório de tamanho k ****/
char *makeRanName(int k){
  int i;
  char *n = malloc((k+1)*sizeof(char));
  for(i=0; i < k; i++) n[i]= 'a'+(char)26*(1.0*rand()/RAND_MAX);
  n[k] = '\0';
  return n;
}
    

/**** gera um vetor com n strings aleatórios de tamanho k *****/
Item* makeRanVector(int n, int k){
  int i;
  Item *v = malloc(n*sizeof(char*));
  for(i=0; i < n; i++){
    v[i] = makeRanName(k);
  }
  return v;    
}    

/**** copia o conteúdo de um vetor *****/
void copyVector(Item v1[], Item v2[], int n){
  int i;
  for(i=0; i < n; i++) v1[i] = v2[i];
}
    
/*****************************************************
*********            bubblesort             **********
*****************************************************/

void bubblesort(Item a[], int n){ 
  int i, j; 
  for(i = 1; i < n; i++)
    for(j = i; j > 0; j--) 
      compexch(a[j-1], a[j]);
}

/*****************************************************
*********          selectionsort            **********
*****************************************************/

void selectionsort(Item a[],int n) { 
  int i, j;
  for(i = 0; i < (n-1); i++){ 
    int min = i;
    for(j = i+1; j < n; j++) 
      if (less(a[j], a[min])) copy(min,j);
      exch(a[i], a[min]);
  } 
}
  

/*****************************************************
*********         selectionsort             **********
*****************************************************/

void insertionsort(Item a[], int n){ 
  int i;
  for(i = 1; i < n; i++) compexch(a[0], a[i]);
  for(i = 2; i < n; i++){ 
    int j = i; Item v; copy(v,a[i]); 
    while(less(v, a[j-1])) { copy(a[j],a[j-1]); j--; }
    copy(a[j],v); 
  } 
}

/*****************************************************
*********             shellsort             **********
*****************************************************/
   
void shellsort(Item a[],int n){ 
  int i, j, h; 
  for(h = 1; h <= (n-2)/3; h = 3*h+1) ;
  for( ; h > 0; h /= 3) 
    for(i = h; i < n; i++){
      int j = i; Item v; copy(v,a[i]); 
      while (j >= h && less(v, a[j-h])){ 
        copy(a[j],a[j-h]); j -= h; 
      }
      copy(a[j],v); 
    }       
}    

/*****************************************************
*********           quicksort               **********
*****************************************************/

int partition(Item a[], int l, int r) { 
  int i = l-1, j = r; Item v = a[r];
  for(;;){ 
    while (less(a[++i], v)) ;
    while (less(v, a[--j])) if (j == l) break;
    if (i >= j) break;
    exch(a[i], a[j]);
  }
  exch(a[i], a[r]);
  return i;
}


void quicksort(Item a[], int l, int r){ 
  int i;
  if (r <= l) return;
  i = partition(a, l, r);
  quicksort(a, l, i-1);
  quicksort(a, i+1, r);
}

/*****************************************************
************ função de intercalação (exemplo) ********
*****************************************************/
void mergeAB(Item a[],Item b[],Item c[],int N,int M){ 
  int i, j, k;
  for(i=0, j=0, k=0; k < N+M; k++){
    if (i == N) { c[k] = b[j++]; continue; }
    if (j == M) { c[k] = a[i++]; continue; }
    copy(c[k],(less(a[i], b[j])) ? a[i++] : b[j++]);
  }
}

/*****************************************************
*********           mergesort               **********
*****************************************************/

/*** vetor auxiliar - deve ser alocado (adiante) ****/
Item *aux;

void merge(Item a[], int l, int m, int r){ 
  int i, j, k;
  for(i = m+1; i > l; i--) copy(aux[i-1],a[i-1]);
  for(j = m; j < r; j++)   copy(aux[r+m-j],a[j+1]);
  for(k = l; k <= r; k++)
    if(less(aux[i], aux[j])) 
      copy(a[k],aux[i++]) else copy(a[k],aux[j--]);
}
  
  
void mergesort(Item a[], int l, int r){ 
  int m = (r+l)/2;
  if (r <= l) return;
  mergesort(a, l, m);  
  mergesort(a, m+1, r);
  merge(a, l, m, r);
}

/*****************************************************
*******              heapsort                 ********
*****************************************************/

fixDown(Item a[], int k, int N)
  { int j;
    while (2*k <= N)
      { j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]); k = j;
      }
  }

#define pq(A) a[l-1+A]
void heapsort(Item a[], int l, int r)
  { int k, n = r-l+1;
    for (k = n/2; k >= 1; k--) 
      fixDown(&pq(0), k, n);
    while (n > 1) 
      { exch(pq(1),pq(n)); 
        fixDown(&pq(0), 1, --n); }
  }
  
/****************************************************/  
  
void printCounters(char *s){
  printf("%s comparacoes: %d char:%d trocas %d atribuicoes: %d\n",
         s,compCount, chCompCount, exchCount, copyCount);
  resetCounters();       
}    

#define N 10000
#define K 100
main(int argc, char *argv[]){
    Item *v = makeRanVector(N,K);
    Item *w = makeRanVector(N,K);  
    resetCounters();

    copyVector(v,w,N);
    bubblesort(v,N);
    printCounters("bubblesort");

    copyVector(v,w,N);
    selectionsort(v,N);
    printCounters("selectionsort");

    copyVector(v,w,N);
    insertionsort(v,N);
    printCounters("insertionsort");

    copyVector(v,w,N);
    shellsort(v,N);
    printCounters("shellsort");

    resetCounters();
    copyVector(v,w,N);
    quicksort(v,0,N-1);
    printCounters("quicksort");

    aux = malloc(N*sizeof(char*));
    copyVector(v,w,N);
    mergesort(v,0,N-1);
    printCounters("mergesort");
    /*********************/
    copyVector(v,w,N);
    heapsort(v,0,N-1);
    printCounters("heapsort");
    system("PAUSE");	
    return 0;
  }