Quicksort error on C

Question

Hi i've coded the following program to input an array of numbers and sort it.

But i still get the wrong answers for numbers such as 1.3333331 !

Whats the problem?!

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

I'm trying to sort the array given that array elements are floating point numbers with up to 8 decimal places ! (Am i using the right algorithm?)

Answer 1

The error you encountered may not be an error in fact, but a misunderstanding of the floating-point type. It is extremely inaccurate especially for the floating-point literals in decimal since they are actually stored in binary. The following code (using your fDig) may be a hint for this inaccuracy:

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

The output of the above code in my gcc (MinGW GCC 4.8.1) with -std=c99 is as follows:

0.3333331
0.33333309999999999
0.33333309999999999329

I could not reproduce the error for the literal 1.3333331.

In short, just double check the suspected floating-point values.

Answer 2

Here is the qsort from "The C Programming Language" by Kernighan & Ritchie, page 87.

Their code originally was int v[] I changed it to double v[] since your data is real numbers. I would not use long long for the indexing variables, the long int will be a 64-bit number allowing for a max index value of 9,223,372,036,854,775,807. If you have an array of doubles going that far, with a double taking up 8 bytes, you would need over 67 million terabytes of 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 );
}