Help me on Quick Sort algorithm

**chatterjee** · 07-17-2009

I'm getting a 'Segmentation fault' program while running the following program.Please help me to find out the error.

Code:

//-------------------------------------------------------------------------
int partition(int a[],int first,int last)
{
int pivot,up,down,i,j,n,pivindex,temp;

up=first;
down=last;
pivot=a[first];



do
{

//move 'up' to the first value > pivot

for(i=0;i<n;i++)
	{
		if(a[i]>pivot)
			up=i;
	}
//move 'down' to the first value <=pivot

for(i=n;i>0;i--)
	{
		if(a[i]<=pivot)
		down=i;
	}
temp=a[up];
a[up]=a[down];
a[down]=temp;
}while(up<=down);

//Swap pivot and a[down]

temp=a[first];
a[first]=a[down];
a[down]=temp;

//Set pivindex at the current position of down 
//so that all values below pivindex are <=pivot 
//and vice versa

pivindex=down; 

return pivindex;

}
//----------------------------------------------------------------------------
void quicksort(int a[],int first,int last)
{
int pivindex;

	if(first<last){
	pivindex=partition(a,first,last);
	quicksort(a,first,pivindex-1);
	quicksort(a,pivindex+1,last);
			}
		
}
//-----------------------------------------------------------------------------
main()
{
int a[20],n;

printf("\nPlease enter the no. of elements::");
scanf("%d",&n);
printf("\nPls enter the array to sorted(quick sort)::");
read_arr(a,n);
printf("\nArray elements are as follows:\n");
print_arr(a,n);
quicksort(a,0,n-1);
printf("\n The Sorted list is:\n");
print_arr(a,n);

}
//-------------------------------------------------------------------------------

**chatterjee** · 07-17-2009

I attach the c file itself.

**MK27** · 07-17-2009

Originally Posted by chatterjee

I'm getting a 'Segmentation fault' program while running the following program.Please help me to find out the error.

Have you tried to locate the line which causes the seg fault?

Do you have access to a debugger?

**tabstop** · 07-17-2009

Your base assumption seems to be that n has a meaningful value inside partition. Why you make this assumption when it is demonstrably false, I don't know.

**iMalc** · 07-17-2009

Even if 'n' did have a meaningful value, the partition step still shouldn't be going over ALL items in the array each time. You need to stop thinking of the function as if you're writing it for the first call, and write it as if it has already been called recursively several times and you're partitioning data somewhere in the middle of your array.
Perhaps performing a quicksort by hand, using say a deck of cards, might help?

**slingerland3g** · 07-17-2009

I have to hit my hand sometime when I see these types posts to prevent me from writing some code down. The jist of the matter is that you should read up on "Algorithms in C - Robert Sedgewick" that really nailed it for me in terms of understanding the sorting algorithms that are out there and how to properly use them.

**BlackOps** · 07-18-2009

here is one of the compact easy to memorize and understand implementations of quicksort.. forgot where i got it:

pivot is selected to be the mid value here

Code:

void quicksort(int a[], int l, int r)
{
    int i=l, j=r;
    int temp;   
    int pivot=a[(l+r)/2]; //pivot value is the mid value

    /* Split the array into two parts */
    do
    {    
        while (a[i] < pivot) i++; 
        while (a[j] > pivot) j--;
        if (i<=j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;
            j--;
        }
    } while (i<=j);

    /* call the functions recursively */
    if (l < j) quicksort(a, l, j);
    if (i < r) quicksort(a, i, r);
}

**MK27** · 07-18-2009

Originally Posted by slingerland3g

The jist of the matter is that you should read up on "Algorithms in C - Robert Sedgewick" that really nailed it for me in terms of understanding the sorting algorithms that are out there and how to properly use them.

I used "Beginning Programming for Dummies" (W. Wang)

.

All of the sort algorithms, including quicksort, can be easily described in a single page using a diagram. The pivot value can make a *huge* difference in the efficiency of the outcome; using a random one (as in BlackOp's example) is the worst way to do it, because the two arrays can easily end up lopsided. A slightly better way would be to take two random values and use the average. Using the actual average would be the best, but ultimately inefficient since that means performing operations on the entire array.

**laserlight** · 07-18-2009

Originally Posted by MK27

The pivot value can make a *huge* difference in the efficiency of the outcome; using a random one (as in BlackOp's example) is the worst way to do it, because the two arrays can easily end up lopsided.

Eh, BlackOp's pivot selection is not random, but rather, fixed as the middle element of the given partition. A randomly selected pivot is actually not bad.

**BlackOps** · 07-18-2009

just selecting a mid value seems ok for me for most of the common sorting problems

**MK27** · 07-18-2009

Originally Posted by laserlight

Eh, BlackOp's pivot selection is not random, but rather, fixed as the middle element of the given partition. A randomly selected pivot is actually not bad.

Since the array has not been sorted, the value of pivot has been selected from the array at random; you might as well just use a[0].

For example, in the series: 2 9 3 1 4 5 7, if I picked 1 as the pivot value, one side will have only one element and the other will have 7. Quick sort will suffer badly if it repeatedly processes lopsided lists because of a random pivot -- sorting a shorter list is expontentially faster (it takes more than twice as long to sort a list twice as long). Way back when I did this

How to sort a simple linked list using swap-sort method

The profile for quicksort was improved like 1000%+ on large lists by using some kind of chosen value for the pivot (I think I did what I said above) vs. a random value from the list.

Originally Posted by BlackOps

just selecting a mid value seems ok for me for most of the common sorting problems

pivot=a[(l+r)/2] is not a "mid value", unless you mean it is just the value in the middle of a series. Which, as I just explained, could be the lowest or highest value in the array -- there is no way to know.

However, if the list is mostly or somewhat sorted it is a good one since quick sort's "worst case" scenario is (generally) the already sorted list.

IMO mergesort is more consistent than quicksort because of stuff like this...

Originally Posted by mk27

Quicksort suffers [...] with ties for the same reason it suffers sorting an already ordered list, which is it's worst case scenario. Because mergesort does not spend time putting a list in order after it's been split off, and instead does it when merging them together, it will benefit if the original list was already in some kind of order, whereas this will only hurt quicksort depending on how the pivot value is choosen. To establish a mean or median value, we must iterate through the list before splitting it -- although in discussions of quicksort I have seen, this process apparently "does not count" as part of it's big O notation. Additional comparisons at each of these iterations would be required as well. Taking the pivot from an already ordered tied list will usually end up on the low side, creating an imbalanced list. Putting pivot ties on the right (opposite the pivot) may improve performance slightly.

**laserlight** · 07-18-2009

Originally Posted by MK27

Since the array has not been sorted, the value of pivot has been selected from the array at random; you might as well just use a[0].

That is a flawed premise: the array could well be sorted or mostly sorted. Quicksort with a randomly selected pivot would be expected to perform roughly the same with any input on average.

Originally Posted by MK27

The profile for quicksort was improved like 1000% on large lists by using some kind of chosen value for the pivot (I think I did what I said above) vs. a random value from the list.

If I know what (fixed) method was used, I can design pathological worst case input for it. With a truly randomly selected pivot, that is not possible (or rather, it is possible, but would not matter since I will only trigger quadratic time performance by luck), and with a pseudorandomly selected pivot, that is only possible if I can determine the state of the PRNG.

**MK27** · 07-18-2009

Originally Posted by laserlight

That is a flawed premise: the array could well be sorted or mostly sorted. Quicksort with a randomly selected pivot would be expected to perform roughly the same with any input on average.

The longer an unsorted list, the less chance it has of resembling something partially sorted. Getting dealt a 10 or 100 or 1000 value run is unlikely, but if the list is only 20 items then 3 values in a row will make a difference.

I was just trying to decifer/remember the stuff from my earlier thread, but I'm almost positive the quicksort I wrote went from taking several minutes to sort millions of strings alphabetically to less than 10 seconds just by tweaking the way the pivot value is chosen; when I say 1000%+ plus improvement I'm not exaggerating. (Obviously, this becomes more and more apparently the longer the list. It will not be notable with only a few hundred items.)

I also recall from reading and googling that a number of people who have written widely used implementations put a lot of stress on the significance of the pivot and how this could make the difference between a weak or mediocre implementation and a real "high performance, best in class" kind of thing.

**laserlight** · 07-18-2009

Originally Posted by MK27

I also recall from reading and googling that a number of people who have written widely used implementations put a lot of stress on the significance of the pivot and how this could make the difference between a weak or mediocre implementation and a real "high performance, best in class" kind of thing.

Yes, that is indeed the case, and it helps if we know the characteristics of the likely input. I am not sure if a randomly selected pivot selection method can be considered "high performance" since there is the same probability of selecting the worst pivot as there is of selecting the best pivot, but characterising it as "the worst way to do it" is wrong, in my opinion.

By the way, when you say "average", you mean median, not mean, right? In such a case, "take two random values and use the average" sounds strange.

**Adak** · 07-18-2009

Thanks for posting that version of Quicksort, BlackOps. It's simplicity somehow makes it shine just a bit brighter, imo.

Thread: Help me on Quick Sort algorithm

Thread Tools

Search Thread

Display

Help me on Quick Sort algorithm

Similar Threads

testing a bubble sort algorithm

STL Sort Algorithm

Straight Insertion Sort function problem

Sorting

Sort algorithm and an ugly error