Problemas com Algoritmo de Ordenação por Inserção Binária

[Diego Koscky 0]

Galera, estou desenvolvendo algoritmos de ordenação e travei nesse Binary Insertion Sort. Criei o algoritmo, compilei (no CodeBlocks) e não acusou nem um erro durante a compilação. Provavelmente há algum erro de lógica, mas não estou conseguindo visualizar. Se puderem me ajudar ficarei grato! Segue em anexo o algoritmo em C++:

 

/* Ordenação por Inserção Binária */

#include <conio.h>
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

//Função para gerar números aleatórios
int inteiros_unif(long *seed, int low, int high) {
   int unif_ret;
   long int m, a, b, c, k;
   double value_0_1;
   m = 2147483647;
   a = 16807;
   b = 127773;
   c = 2836;
   k = *seed/b;
   *seed = a * (*seed % b) - k * c;
   if (*seed < 0)
   *seed = *seed + m;
   value_0_1 = (double) *seed / m;
   unif_ret = low + value_0_1 * (high - low + 1);
   return (unif_ret);
}

int BinarySearch (int a[], int low, int high, int key) {
   int mid;

   mid = low + ((high - low) / 2);

   if (key > a[mid])
       return BinarySearch (a, mid + 1, high, key);
   else if (key < a[mid])
       return BinarySearch (a, low, mid, key);

   return mid;
}


int BinaryInsertionSort (int a[], int n) {

   int trocas = 0;
   int ins, i, j;
   int tmp;

   for (i = 1; i <= n; i++) {
       ins = BinarySearch (a, 0, i, a[i]);
       if (ins < i) {
           tmp = a[i];
           for (j = i - 1; j >= ins; j--)
               a[j + 1] = a[j];
           a[ins] = tmp;
           trocas++;
       }
   }
   return trocas;
}


int main(){

   int minimo          = 0;
   int maximo          = 100000;
   long semente        = 1234554321;
   int MAX_ELEMENTS    = 500;
   int lista[MAX_ELEMENTS];
   int troca = 0;

   //preenche o vetor com os números aleatórios
   for(int i = 1; i <= MAX_ELEMENTS; i++){
       lista[i] = inteiros_unif(&semente,minimo,maximo);
   }

   troca = BinaryInsertionSort(lista,MAX_ELEMENTS);

   for(int i = 0; i < MAX_ELEMENTS; i++){
       printf("$d\n",lista[i]);
   }

   printf("Trocas: %d\n\n",troca);

   return 0;
}

[Mateus GP 13]

Troque seu BinarySearch, por este:

int BinarySearch (int a[], int low, int high, int key)
{
   int mid;

   if (low == high)
       return low;

   mid = low + ((high - low) / 2);

   if (key > a[mid])
       return BinarySearch (a, mid + 1, high, key);
   else if (key < a[mid])
       return BinarySearch (a, low, mid, key);

   return mid;
}

 

Ocorreu algo inusitado quando pesquisei sobre este algoritmo, Veja: http://jeffreystedfast.blogspot.com.br/2007/02/binary-insertion-sort.html