Runtime Error in Quick Sort Program

Question

challarao 0 Junior Poster in Training

14 Years Ago

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");

}

algorithm-pseudocode c

3 Contributors
10 Replies
470 Views
13 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by challarao

Dani AI

Generated 9 Months Ago

Good progress — the symptoms and the fixes described in the thread point to the usual root causes. correctly spotted the pivot/index confusion and the potential for infinite loops; was right to suggest simple printf debugging. Below is a compact checklist and practical advice to make your quicksort robust and avoid segmentation faults.

Be explicit about pivot vs pivot index. Either keep a pivot index and always use a[pivotIndex], or copy the value with pivotVal = a[left] and compare against pivotVal. Mixing the two is a frequent source of wrong array accesses.
Prevent out-of-bounds increments. In the partition loop guard the pointer moves so i never runs past right and j never runs before left (for example, check i <= right and j >= left in the while conditions). Unguarded i++/j-- on bad data will read/write outside the array and segfault.
Handle equal elements safely. Use <= / >= carefully so duplicates don’t produce an endless loop. A common pattern is to advance i while a[i] <= pivotVal and decrement j while a[j] >= pivotVal, then swap only when i < j.
Make return types and prototypes consistent. If quick doesn’t return a meaningful value, declare it void quick(...). Partition must return the final pivot index; not returning a value is undefined behavior.
Watch recursion and stack use. Worst-case pivot choices can cause deep recursion and stack overflow for large n. For big arrays use an iterative approach, randomize/median-of-three pivot selection, or allocate the array on the heap (malloc) instead of a large VLA on the stack.

Debugging workflow: compile with warnings (gcc -std=c11 -Wall -Wextra -g), add diagnostic printf lines for left,right,i,j,pivot inside partition, and run under valgrind or gdb to catch invalid reads/writes and get a backtrace. Test small, easy cases (sorted, reverse, many duplicates) — they often reveal logic errors quickly.

Final note: the change you reported (using pivot = a[left] and returning the partition index) is the correct conceptual fix. Clean up the function signatures, add bounds guards, and enable compiler warnings to prevent relapse.

All 10 Replies

Member #907664

14 Years Ago

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

Adak 419 Nearly a Posting Virtuoso

14 Years Ago

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.

Member #907664

14 Years Ago

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.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

challarao 0 Junior Poster in Training · Answer 1 · 2011-11-02T17:16:20+00:00

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 0 Junior Poster in Training · Answer 2 · 2011-11-02T17:18:03+00:00

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

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

challarao 0 Junior Poster in Training · Answer 3 · 2011-11-02T17:18:54+00:00

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....

Adak 419 Nearly a Posting Virtuoso · Answer 4 · 2011-11-02T20:26:52+00:00

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 0 Junior Poster in Training · Answer 5 · 2011-11-02T20:48:25+00:00

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 419 Nearly a Posting Virtuoso · Answer 6 · 2011-11-02T21:30:24+00:00

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 0 Junior Poster in Training · Answer 7 · 2011-11-02T21:39:47+00:00

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");

}

Runtime Error in Quick Sort Program

Dani AI

Recommended Answers Collapse Answers

All 10 Replies

Recommended Answers