Saturday, 23 April 2011

C/C++ : Quick Sort

Here is the source code of quick sort. This algorithm also knowns as most efficient search algorithm.
I don't know why but it doesn't work appropriately. It works on 100 data but more than that it crushes.
If you find bug let me know, thank you.

I've used Hoare-partition
Here is the code.

int partition( int a[ ]int low, int high )
{
    int piwot, right, left;
    left = low + 1 ;
    right = high ;
    piwot = alow ];
    while(1)
    {
        while( aright ] > piwot ) right--;
        while( a[ left ] < piwot &&a left < high ) left++;
        if ( left < right )
            swap( a, left, right );
        else{
            swap( a, low, right );
            return right;
        }
    }
}

void quickSort( int a[ ]int low, int high)
{
    int part;
    if( low &lt; high )
    {
        part = partition( a, low, high );
        quickSort( a, low, part -1 );
        quickSort( a, part +1, high );
    }
}

1 comment: