sorte d'insertion binaire du tableau ne fonctionne pas (code en C)

Question

Voici mon code:

#include <stdio.h> 
#define SIZE 4 
int main(int argc, const char * argv[]) 
{ 
double m[SIZE],tmp; 
int i,min,max,c,k,l,pos; 
for (i=0; i<SIZE; i++) { 
    printf("a%d? ",i); 
    scanf("%lf",&m[i]); 
} 
for (i=0; i<SIZE; i++) 
    printf("%.1lf ",m[i]); 
printf("\n"); 
k = 1; 
//======================== 
do { 
    min = 0; 
    max = k-1; 
    do 
    { 
     c = (min+max)/2; 
     if (m[c]>m[k]) 
     { 
      min=c; 
     } 
     else { 
      max=c; 
     } 
     c = (min+max)/2; 
    } 
    while(min != c); 
    pos = min; 
    if(m[pos]<m[k]) 
    { 
      pos++; 
    } 
    tmp = m[k]; 
    l=k; 
    while (l>pos) { 
     m[l]=m[l-1]; 
     l--; 
    } 
    m[pos]=tmp; 
    k++; 
} while (k != SIZE); 
for (i=0; i<SIZE; i++) 
    printf("%.1lf ",m[i]); 
//======================== 
return 0; 

}

peut aider quelqu'un, pourquoi pas le tri des œuvres? Le code est correct, comme je le pense. Peut-être que je suis avec l'algorithme? J'essaie d'utiliser le tri d'insertion binaire. Ou quelqu'un peut-il donner une alternative au code C (pour voir ce qui est incorrect)?

Answer 1

L'algorithme abstrait pour insertion sort est:

function insertionSort(array A) 
    for i from 1 to length[A]-1 do 
     value := A[i] 
     j := i-1 
     while j >= 0 and A[j] > value do 
      A[j+1] := A[j] 
      j := j-1 
     done 
     A[j+1] = value 
    done 

La mise en œuvre dans C, nous avons:

void binaryInsertionSort (int a[], int n) 
    { 
    register int i, m; 
    int hi, lo, tmp; 

    for (i = 1; i < n; i++) { 
     lo = 0, hi = i; 
     m = i/2; 

     do { 
      if (a[i] > a[m]) { 
       lo = m + 1; 
      } else if (a[i] < a[m]) { 
       hi = m; 
      } else 
       break; 

      m = lo + ((hi - lo)/2); 
     } while (lo < hi); 

     if (m < i) { 
      tmp = a[i]; 
      memmove (a + m + 1, a + m, sizeof (int) * (i - m)); 
      a[m] = tmp; 
     } 
    } 
} 

Answer 2

essayez ceci:

void binaryInsertionSort (int *array, size_t size) { 
register int i, middle; 
int high, low, tmp; 
static int comparisonCount = 0, swapCount = 0; 
i = 1; 
while (i < size) { 
    low = 0, high = i; 
    middle = i/2; 

    do { 
    if (array[i] > array[middle]) { 
     low = middle + 1; 
    } else if (array[i] < array[middle]) { 
     high = middle; 
    } else 
     break; 

    middle = low + ((high - low)/2); 
    } while (low < high); 

    comparisonCount++; 
    if (middle < i) { 
    tmp = array[i]; 
    memmove (array + middle + 1, array + middle, sizeof (int) * (i - middle)); 
    swapCount++; 
    array[middle] = tmp; 
    } 
    i++; 
} 
printf("Comparison:%d Swap: %d\n", comparisonCount, swapCount); 
}