C上的快速排序錯誤

Question

嗨，我編了下面的程序來輸入一個數組的數組並對其進行排序。

但我仍然得到錯誤的答案，如1.3333331數字！

什麼問題？

#include <stdio.h> 

void quicksort(double array[], long long left, long long right); 

long long partition(double array[], long long left, long long right); 

int fDig(double x); 

int main(void) { 
    long long quantity = 0LL, counter = 0LL; 
    int dig = 0; 
    scanf("%lli", &quantity); 

    double beard[quantity]; 

    for(counter = 0LL; counter < quantity; counter++) { 
     scanf("%lf", &beard[counter]); 
    } 

    quicksort(beard, 0LL, quantity - 1LL); 

    for(counter = 0LL; counter < quantity; counter++) { 
     dig = fDig(beard[counter]); 
     printf("%.*lf", dig, beard[counter]); 
     if(counter == quantity - 1LL) { 
      break; 
     } 

     printf(" "); 
    } 

    return 0; 
} 

int fDig(double x) { 
    int result = 0; 
    while(x != floor(x)) { 
     x *= 10; 
     result++; 
    } 

    return result; 
} 

/* Quick sort recursive function */ 

void quicksort(double array[], long long left, long long right){ 
    if (left < right) { 
     long long middle = partition(array, left, right); 
     quicksort(array, left, middle - 1LL); 
     quicksort(array, middle + 1LL, right); 
    } 
} 

/* Partition : 
    Modifies the array : 
    SMALLER , PIVOT , GREATER 
    Returns the index for pivot because pivot is placed in the final position 
*/ 

long long partition(double array[], long long left, long long right) { 
    long long middle; 

    double x = array[left]; 
    long long l = left; 
    long long r = right; 

    while(l < r) { 
     while((array[l] <= x) && (l < right)) { 
      l++; 
     } 

     while((array[r] > x) && (r >= left)) { 
      r--; 
     } 

     if(l < r) {  
      double temp = array[l]; 
      array[l] = array[r]; 
      array[r] = temp; 
     } 
    } 

    middle = r; 

    double temp = array[left]; 
    array[left] = array[middle] ; 
    array[middle] = temp; 

    return middle ; 
} 

我想對數組進行排序，因爲數組元素是浮點數最多8位小數！ （現在用我正確的算法？）

Answer 1

下面是Kernighan的&裏奇從「C程序設計語言」的快速排序，第87頁

他們的代碼原本是int v[] 我改成了double v[]因爲您的數據是實數。 我不會使用long long作爲索引變量，long int將是一個64位數字，允許最大索引值爲9,223,372,036,854,775,807。如果你有一堆雙打，那麼雙倍佔用8個字節，你將需要超過6700萬兆字節的內存。

void swap (double v[], long int i, long int j) 
{ 
    double temp; 

    temp = v[i]; 
    v[i] = v[j]; 
    v[j] = temp; 
} 


void qsort (double v[], long int left, long int right) 
{ 
    long int i; 
    long int last; 

    if (left >= right) 
     return; /* do nothing if array contains fewer than 2 elements */ 

    swap(v, left, (left+right)/2); /* move partition element */ 
    last = left; 
    for (i = left + 1; i <= right; i++) 
    { 
     if (v[i] < v[left]) 
     swap(v, ++last, i); 
    } 
    swap(v, left, last); 
    qsort(v, left, last - 1); 
    qsort(v, last + 1, right); 
} 

Answer 2

您遇到的錯誤實際上可能不是錯誤，而是對浮點類型的誤解。這是非常不準確的，特別是對於十進制浮點文字，因爲它們實際上是以二進制形式存儲的。下面的代碼（使用fDig）可以是用於這種不精確性一個提示：

#include <stdio.h> 
#include <math.h> 

int fDig(double x) { 
    int result = 0; 
    while (x != floor(x)) { 
     x *= 10; 
     result++; 
    } 

    return result; 
} 

int main() { 
    double x = 0.3333331; 

    int dig = fDig(x); 
    printf("%.7f\n", x); 
    printf("%.*f\n", dig, x); 
    printf("%.20f\n", x); 

    return 0; 
} 

上述代碼在我的gcc（MinGW的GCC 4.8.1）與-std = C99的輸出如下所示：

0.3333331 
0.33333309999999999 
0.33333309999999999329 

我無法重現文字1.3333331的錯誤。

總之，只需再次檢查可疑的浮點值。