c - 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 位小数的 float ，我正在尝试对数组进行排序! (我使用的算法正确吗？)

Answer 1

这是来自 Kernighan & Ritchie 的“The C Programming Language”，第 87 页的 qsort。

他们的代码最初是int v[]我将其更改为 double v[] 因为您的数据是实数。我不会将 long long 用于索引变量，long int 将是一个 64 位数字，允许的最大索引值为 9,223,372,036,854,775,807。如果你有一个 double 数组那么远，一个 double 占用 8 个字节，你将需要超过 6700 万太字节的 ram。

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 );
}