Thread: quick sort program

hey friends!!!! Quicksort algorithm is simple but its implementation is really confusing. I have tried to write a program for quick sort with some help of textbook but the program has some logical error and am not able to find it out.
Can you help it out.The code is:

Code:

#include<stdio.h>
#include<stdlib.h>
void printlist(int *x,int n);
void quicksort(int *x,int lower,int upper);
void swap(int *a,int *b);
int main()
{
	int *arr,n,i,resp;
	printf("\nHOW MANY ELEMENTS?\t");
	scanf("%d",&n);
	arr=(int*)malloc(n*sizeof(int));
	printf("\n\nWOULD YOU LIKE TO GENERATE NUMBERS RANDOMLY OR YOURSELF?\n");
	printf("PRESS 1 FOR RANDOM NUMBERS\n      2	FOR INPUTTING NUMBERS\n");
	gen:
	scanf("%d",&resp);
	switch(resp)
	{
		case 1:
			printf("\nOK THEN. NOW GENERATING RANDOM NUMBERS.....\n");
			for(i=0;i<n;i++)
			{
				arr[i]=rand()/100;
				//printf("\nELEMENT NO. %d:\t%d ",i+1,arr[i]);
			}
			break;
		case 2:
			printf("\nPLEASE ENTER THE ELEMENTS:\n");
			for(i=0;i<n;i++)
			{
				printf("\nELEMENT NO. %d: ",i+1);
				scanf("%d",&arr[i]);
			}
			break;
		default:
			printf("\nERROR-UNEXPECTED INPUT");
			goto gen;
			break;
	}
	printf("\n\nTHE LIST BEFORE SORTING IS(UNSORTED LIST):\n");
	printlist(arr,n);
	quicksort(arr,0,n-1);
	printf("\n\nTHE LIST AFTER SORTING IS(SORTED LIST):\n");
	printlist(arr,n);
	return 0;
}

void printlist(int *x,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		printf("%d  ",x[i]);
	}
}
void quicksort(int *x,int lower,int upper)
{
	int lo,hi,i,pivot;
	pivot=x[lower];
	lo=lower+1;
	hi=upper;
	while(lo<=hi)
	{
		while(x[lo]<pivot)
			lo++;
		while(x[hi]>pivot)
			hi--;
		if(lo<hi)
			swap(&x[lo],&x[hi]);
	}
	swap(&x[lower],&x[hi]);
	quicksort(x,lower,hi-1);
	quicksort(x,hi+1,upper);
	return;
}
void swap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

Can u find out any fault in the code???

Not sure if you're qsort'ng the array index or the contents?

Code:

if(lo<hi)
         swap(&x[lo],&x[hi]);

Originally Posted by itCbitC

Not sure if you're qsort'ng the array index or the contents?

Code:

if(lo<hi)
         swap(&x[lo],&x[hi]);

But that doesn't seems to be the part of the problem. I tried it out but no effect....

Originally Posted by rakeshkool27

But that doesn't seems to be the part of the problem. I tried it out but no effect....

What did you change it to?

Originally Posted by tabstop

What did you change it to?

I changed to x[lo]<x[hi].

Originally Posted by rakeshkool27

I changed to x[lo]<x[hi].

What you had the first time is correct -- lo points to the first high element in the low half, and hi points to the last low element in the high half, and as long as lo hasn't passed hi (i.e., if lo < hi) you want to swap.

Also at some point you need to do a "hey I'm out of data" check -- running your code led to a segfault when the recursive call reached lower = 0, upper = -2389.