CODEWITHSUNDEEP
cquicksort
user2896235
user2896235

Reputation: 359

What's wrong with this quick-sort program?

I have written the below program for quick-sort. However, it doesn't seem to be working. Can some one point what's wrong with this program?

#include<stdio.h>

void swap (int a[], int left, int right) {
    int temp;
    temp=a[left];
    a[left]=a[right];
    a[right]=temp;
} 

void printarray(int a[], int);
void partition( int a[], int low, int high );

void quicksort( int a[], int low, int high ) {
    srand((unsigned int)time(0));
    partition( a, low, high );
} 

void partition( int a[], int low, int high ) {
    int left, right;
    int pivot_item, pivot;

    left = low;
    right = high;

    if ((right - left) <= 1)
        return;

    pivot = rand() % (high - low + 1);
    pivot_item = a[pivot];

    while (left < right) {
        while (a[left] <= pivot_item)
            left++;

        while (a[right] > pivot_item)
            right--;

        swap(a,left,right);
    }

    partition(a, low, right-1);
    partition(a, right+1, high);

    return;
}

int main() {
    int a[] = {24, 5, 3, 35, 14, 23, 19, 43, 2, 1};
    int i, n = 10;

    printf("\nUnsorted elements: \n");
    printarray(a,n);
    quicksort(a,0,n-1);
    printf("\nSorted elements: \n");
    printarray(a,n);

}


void printarray(int a[], int n) {
    int i;

    for (i = 0; i < n; i++)
        printf(" %d ", a[i]);
    printf("\n");
}

Each time I get different outputs as below.

:>~/prgms$ ./a.out 

Unsorted elements: 
 24  5  3  35  14  23  19  43  2  1 

Sorted elements: 
 14  2  19  1  5  23  43  35  3  24 

:>~/prgms$ ./a.out 

Unsorted elements: 
 24  5  3  35  14  23  19  43  2  1 

Sorted elements: 
 1  5  35  14  23  19  3  24  43  2

Upvotes: 1

Views: 187

Answers (2)

Armali
Armali

Reputation: 19375

In addition to the error pointed out by stark, which can be fixed by changing

pivot = rand() % (high - low + 1);

to

pivot = low + rand() % (high - low + 1);

there are two more errors. First,

    while( a[left] <= pivot_item )
    left++;

should be

    while (a[left] < pivot_item) left++;

otherwise, the index left can increment beyond the pivot position and even the end of the array, leading to undefined results. Second,

if ((right - left) <= 1)
return;

should be

if (right - left < 1) return;

otherwise, partitions of length 2 were not sorted.

Upvotes: 3

stark
stark

Reputation: 13189

In partition, pivot is taken from the range 0..(high-low+1). It should be taken from the range low..high.

Upvotes: 2

Related Questions