Page 1 of 1

Quick Sort: Everything You Wanted to Know A description, implementation, analysis, and basic information about t Rate Topic: ***** 1 Votes

#1 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 13
  • View blog
  • Posts: 548
  • Joined: 17-October 07

Posted 10 July 2008 - 06:18 PM

Introduction

This is a tutorial on the sorting algorithm “Quick Sort”, an essential algorithm in the field of computer science. Quick Sort is one of the easiest algorithms to code and implement as well as one of the quickest (with a name like Quick Sort who would have thought?). Throughout this tutorial I will give valuable information on what Quick Sort does, how it obtains its result, running time efficiency, etc. So sit back, relax, and enjoy the humble Quick Sort:

What is Quick Sort Anyway?

Quick Sort is the fastest known generic sorting algorithm in practice. The method in which the data is obtained and sorted is through what we call a “Divide and Conquer” method. Let’s elaborate a bit more on this idea:

Divide: The initial problem is broken down into sub-problems.
Conquer: The sub-problems are “conquered” or solved.
Combination: The solutions of the initial problem and sub-problems are combined.


Does the “Divide and Conquer” mentality sound a bit familiar? If you’ve dealt with the idea of recursion it most certainly should ring a bell or two. Recursion is obtained through the same way of thinking and breaking down a problem and rightfully so because Quick Sort is a recursive algorithm.

So what we have looked at is the basic strategy, now we take a brief look at how the Quick Sort algorithm itself works. The basic algorithm to sort an array S consists of the following four steps:

1. If the number of elements in S is 0 or 1, then return. (Base case)
2. Pick any element in v in S. This is called the pivot.
3. Partition S – {v} (the remaining elements in S) into 2 separate groups:
S1 = {x Є S – {v} xv}, and S2 = {x Є S – {v} | xv}.
4. Return {quicksort(S1) followed by v, followed by quicksort(S2)}.


Notice that “partition” and “pivot” are bold these are new key words of which are essential to Quick Sort. I will elaborate on these throughout the next two sections.


Choosing the Pivot Point

The pivot point as described above is the point in the data set which separates the elements into two groups focusing on the pivot point. A visual example may help at this time:

[ 1 5 3 2 4 ]

As we can see, the pivot in this case 3, is in the middle of two sets of numbers on either side. Don't think that the pivot point must be the middle, in fact it can be any position in the data set. However there are some right and wrong choices when it comes to actually picking the pivot.

:angry: A Bad Method :v:

A rule of thumb is to never pick the first element in the data set as the pivot. This method is acceptable if the input is random (still don't do it) but if it's say in reverse order the pivot partitions the data in the most inefficient way possible, prompting the Quick Sort to run in quadratic time which is awful compared to what it should be doing. Another no no is picking the largest data item in a set. This in short has the same bad effects as picking the first element. Make a note not to do either.

:crazy: A Better Method :v:

A better method tends to be picking a pivot point at random. This is a fairly safe bet unless the random number generator has some type of flaw. However, this is not quite the best method either because random number generation is an expensive operation to use, thus hurting the running time of the Quick Sort.

:D The Best Method :^:

So what's the best method you say? Well the best choice of pivot would be the median of the array. Unfortunately this is hard to calculate and would slow down the algorithm considerably. The best way to do it from there would be to pick the first number, the last number, and the middle number within the data set to calculate the median. So in the following data set:
[ 8 1 4 9 6 3 5 2 7 0 ]

The left element would be 8, the right 0, and the middle would be 6. Thus the pivot would be 6. This as can easily be seen, eliminates the bad cases.


Partitioning


We now get to the next bold word "Partitioning". In the world of Quick Sort there are many different partitioning strategies used in practice, hence the following way will not be the only way to do it however our method is known to yield good results. The first step is to get the pivot point out of the way by swapping it with the last element. "i" starts at the first element and "j" starts at the next to last element. We will use the same input as described in the previous section:

"i:" Is Blue
"j:" Is Red
[ 8 1 4 9 0 3 5 2 7 6 ]

While "i" is to the left of "j" we move "i" right, skipping over elements that are less than the pivot point. We move"j" left, skipping over elements that are greater than the pivot point. When "i" and "j" have stopped, "i" is pointing at a large element and "j" is pointing at a small element. If "i" is to the left of "j" those elements are swapped. The point is to push a big element to the right side and a lesser element to the left side. Looking above at the data set of numbers, "i" remains stable and "j" moved over one place. The following steps are laid out for you to follow:
[ 8 1 4 9 0 3 5 2 7 6 ]

We now swap the elements pointed to "i" and "j" and repeat the process until "i" and "j" cross each other

After the First Swap

[ 2 1 4 9 0 3 5 8 7 6 ]

Before the Second Swap

[ 2 1 4 9 0 3 5 8 7 6 ]

After the Second Swap
[ 2 1 4 5 0 3 9 8 7 6 ]

Before the Third Swap

[ 2 1 4 5 0 3 9 8 7 6 ]

It is at this point in the algorithm that "i" and "j" have crossed, hence no swaps are done. The final part then, would be to swap the pivot point (in our case "9" ) with "i"

After Pivot Swap
[ 2 1 4 5 0 3 6 8 7 9 ]

Once the pivot point is swapped with "i", we can be sure that all of the other elements that are less than "i" must be small. Likewise this holds true for elements to the right of "i" which must be large.

The Code


Now we will take a look at the actual implementation of the code itself. It should be fairly simple to follow if you understand the ideas and concepts expressed in the previous sections of this tutorial. First I will provide the code for finding the median which selects the pivot point in the way described above:

Code to determine the median partitioning:
template <typename T>
const T &median( vector<T> &data, int right, int left ){
	int middle = ( right + left ) / 2;
	
	if ( data[middle] < data[left] )
		swap( data[left], data[middle] );
	if ( data[right] < data[middle] )
		swap( data[middle], data[right];
	if ( data[right] < data[left] )
		swap( data[left], data[right];

	swap( data[middle], data[right - 1];
	
	return data[right - 1];
}



Main Quick Sort Code:
template <typename T>
void quickSort( vector<T> &data, int right, int left ){
	
	if ( left + 10 <= right ){
		T pivot = median( data, right, left );

		int i = left, j = right - 1;
		while (true){
			while ( data[++i] < pivot ){}
			while ( pivot < data[--j] ) {}
			
			if ( i < j )
				swap( data[i], data[j] );
			else
				break;
		}//end while

		swap( data[i], data[right - 1] );

		quickSort( data, left, i - 1 );
		quickSort( data, i + 1, right );

	}//end if

	else
		insertionSort( data, left, right );
}



Analysis & Conclusion of Quick Sort


Quick Sort, as we have found out is quite the algorithm. Not only is it the fastest but it's also extremely efficient. A short note however, for small sets of data, Quick Sort will be out performed by routines such as Insertion Sort so when choosing between algorithms for sets of data make sure to keep this tidbit in mind. A programmer must strategically analyze what is put in front of him and use the appropriate methods. With that said let us take a brief look at the Big-Oh notation for the worst, best, and average cases.

Worst Case Analysis:
The worst case in Quick Sort gives a Big-Oh notation of O( N * N ) or N squared

Average Case Analysis:
The average case will yield O(N log N)

Best Case Analysis:
The best case will also yield a Big-Oh analysis of O(N log N)

Well I hope you enjoyed my humble homage to the Quick Sort algorithm, thank you for reading.

Is This A Good Question/Topic? 4
  • +

Replies To: Quick Sort: Everything You Wanted to Know

#2 born2c0de  Icon User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 180
  • View blog
  • Posts: 4,667
  • Joined: 26-November 04

Posted 10 July 2008 - 10:52 PM

Brilliant :^:
Approved.
Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • Joined: 29-May 08

Posted 10 July 2008 - 11:21 PM

Great Tutorial :^:
The Worst Case 10 9 8 7 6 5 4 3 2 1
Was This Post Helpful? 0
  • +
  • -

#4 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 13
  • View blog
  • Posts: 548
  • Joined: 17-October 07

Posted 11 July 2008 - 04:57 AM

View Postborn2c0de, on 10 Jul, 2008 - 10:52 PM, said:

Brilliant :^:
Approved.


Very flattered, thank you very much. What can I say, I learn from the best!

View PostAdamSpeight2008, on 10 Jul, 2008 - 11:21 PM, said:

Great Tutorial :^:
The Worst Case 10 9 8 7 6 5 4 3 2 1


Thank you very much Adam, although I must say you are the VB king! Good job to all of your work as well
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1