Runtime Error in Quick Sort Program

[challarao]

Hi....
I wrote a program for Quick Sort algorithm....
It is compiled fine....but it is giving a run time error i.e., Segmentation Fault....
I tried hard but couldn't find out what is that thing causing segmentation error in this program....
Please help....
I'm getting segmentation fault very frequently (i'm using gcc compiler).....why?
Any help would be highly appreciated...
Code

#include<stdio.h>
int quick(int a[],int left,int right){
	
	if(left<right){
		int newpivi;
		newpivi=partition(a,left,right);	//positioning pivot in its correct position.......
		quick(a,left,newpivi-1);		//left part of the pivot element....
		quick(a,newpivi+1,right);		//right part of the pivot element.....
		}
}
int partition(int a[],int left,int right){			//partition function for positioning pivot
		int pivot=left,big=left+1,small=right,temp=0;	//left most element is selected as pivot
		do {
		while(a[pivot]>=a[big])
				big++;
		while(a[pivot]<=a[small])
				small--;
		if(big<small){
			temp=a[big];
			a[big]=a[small];
			a[small]=temp;
			}
		
			
		}while(small>big);
		temp=a[small];
		a[small]=a[pivot];
		a[pivot]=temp;
	
}
main(){
int i,j,key;
int n;
printf("Enter size:");
scanf("%d",&n);
int a[n];
printf("\n Enter elements:\n");
for(j=0;j<n;j++)
	scanf("%d",&a[j]);
quick(a,0,n-1);						//calling quick sort function
print(&a,n);		
}
print(int *a,int p){					//function for printing the array elements
	int i;
	for(i=0;i<p;i++)
		printf("%d ",a[i]);
	printf("\n");

}

Does it say where the segmentation fault occurs? Have you tried debugging?

[Adak]

Try <= in your comparisons. Without at least one of them in in that if statement, my version of Quicksort, goes into an endless loop.

/* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) { //without the = in there, it's an endless loop
      temp= A[i];
      A[i]= A[j];
      A[j]=temp;
      i++;
      j--;
    }
  } while (i<=j);

I have to say, naming a variable "big" when it has to be incremented repeatedly, and naming another "small" when it can only be decremented, is some crazy naming scheme. I'd swap those two names, just for a bit more clarity.

[challarao]

Try <= in your comparisons. Without at least one of them in in that if statement, my version of Quicksort, goes into an endless loop.

/* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) { //without the = in there, it's an endless loop
      temp= A[i];
      A[i]= A[j];
      A[j]=temp;
      i++;
      j--;
    }
  } while (i<=j);

I have to say, naming a variable "big" when it has to be incremented repeatedly, and naming another "small" when it can only be decremented, is some crazy naming scheme. I'd swap those two names, just for a bit more clarity.

I tried adding <= and it didn't work......it is still giving me segmentation fault

#include<stdio.h>
int quick(int a[],int left,int right){
	
	if(left<right){
		int newpivi;
		newpivi=partition(a,left,right);	//positioning pivot in its correct position.......
		quick(a,left,newpivi-1);		//left part of the pivot element....
		quick(a,newpivi+1,right);		//right part of the pivot element.....
		}
}
int partition(int a[],int left,int right){			//partition function for positioning pivot
		int pivot=left,i=left+1,j=right,temp=0;	//left most element is selected as pivot
		do {
		while(a[i]<=a[pivot])
				i++;
		while(a[pivot]<=a[j])
				j--;
		if(i<=j){
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			}
		
			
		}while(i<=j);
		temp=a[j];
		a[j]=a[pivot];
		a[pivot]=temp;
	
}
main(){
int i,j,key;
int n;
printf("Enter size:");
scanf("%d",&n);
int a[n];
printf("\n Enter elements:\n");
for(j=0;j<n;j++)
	scanf("%d",&a[j]);
quick(a,0,n-1);						//calling quick sort function
print(&a,n);		
}
print(int *a,int p){					//function for printing the array elements
	int i;
	for(i=0;i<p;i++)
		printf("%d ",a[i]);
	printf("\n");

}

I tried deleting

quick(a,newpivi+1,right);

from the function, then it did n't give me any segmentation fault.....what's wrong with my program?

[challarao]

Does it say where the segmentation fault occurs? Have you tried debugging?

I tried some manipulations they didn't work....

[challarao]

Does it say where the segmentation fault occurs? Have you tried debugging?

I tried some manipulations they didn't work....I think we won't get any detailed information for runtime errors....

What you should then do is add additional printf() statements in your code to help you debug the problem. I would print index values, array values, etc. to help isolate the issue, then continue on from there.

[Adak]

You're using A[pivot], instead of using the value of the pivot itself. When I do that, my Quicksort crashes as well.

Look again at the code I posted - pivot is a value, not an index.

[challarao]

You're using A[pivot], instead of using the value of the pivot itself. When I do that, my Quicksort crashes as well.

Look again at the code I posted - pivot is a value, not an index.

Yeah, that's the problem...and another problem is also there which is actually causing( I think) the problem, that partition function is not returning anything in my code....
I got a doubt now.When I don't give a return statement in partition function, what might be the value assigned to the variable 'newpivi' in the 'quicksort' function.....?

[Adak]

The value of a variable assigned the return value from a function - when there is no value returned (if I understood your question OK), will remain unchanged, but it's easy enough to test it - and don't be afraid to do that.

Different compilers, and computers, are NOT the same, and there are LOTS of differences which are still OK with the standards for C. They're undefined, and so almost anything is allowed.

[challarao]

Thanks for all replies....
After doing some manipulations and putting a return value, my program is working fine....
Here is my final code.........

#include<stdio.h>
int quick(int a[],int left,int right){
	
	if(left<right){
		int newpivi;
		newpivi=partition(a,left,right);	//positioning pivot in its correct position.......
		quick(a,left,newpivi-1);		//left part of the pivot element....
		quick(a,newpivi+1,right);		//right part of the pivot element.....
		}
}
int partition(int a[],int left,int right){			//partition function for positioning pivot
		int pivot=a[left],i=left+1,j=right,temp=0;	//left most element is selected as pivot
		do {
		while(pivot>a[i])
				i++;
		while(pivot<a[j])
				j--;
		if(i<j){
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			}
		
			
		}while(j>i);
		temp=a[j];
		a[j]=pivot;
		a[left]=temp;
		return j;
}
main(){
int i,j,key;
int n;
printf("Enter size:");
scanf("%d",&n);
int a[n];
printf("\n Enter elements:\n");
for(j=0;j<n;j++)
	scanf("%d",&a[j]);
quick(a,0,n-1);						//calling quick sort function
print(&a,n);		
}
print(int *a,int p){					//function for printing the array elements
	int i;
	for(i=0;i<p;i++)
		printf("%d ",a[i]);
	printf("\n");

}