Arun is a curious programmer who has spent the last 9 years trying to create better and faster programs. When the sun goes down, he experiments with various technologies and programming languages. He blogs at http://rerun.me. Arun is a DZone MVB and is not an employee of DZone and has posted 20 posts at DZone. You can read more from them at their website. View Full User Profile

Quicksort - the Easy Way

09.07.2012
| 12807 views |
  • submit to reddit

Quick sort is the fastest known comparision sort for arrays. To top it, it could be done in-place for arrays. For Linked Lists, Merge Sort might be a better option. Also since Quicksort improves its performance by using random numbers, it also becomes an example of a breed of algorithms named “Randomized Algorithms”.

The naive version of the Algorithm goes like this :

1)  Start with list I of n items
2)  Choose pivot v from I
3)  Partition I into 2 unsorted lists I1 and I2 such that
        I1 : all keys smaller than pivot
        I2 : all keys larger than pivot
        Items same as pivot goes to either list
4)  Sort I1 recursively, yielding sorted list S1
5)  Sort I2 recursively, yielding sorted list S2
6)  Concatenate S1,v,S2 yielding sorted list S
Pseudocode in a Video

 

How Long does Quick sort take ?

Interestingly, Quicksort has a worst case running time of 0(n2). However, with careful implementations, n2 never happens and it almost always runs in 0(n log n). As compared to Heapsort, whose best and worst case is guaranteed to be n log n, Quicksort beats Heapsort in clock time for two reasons :

1) The constant factor surrounding the 0(nlogn) is lesser than Heapsort due to the very thin core logic. Heap sort’s detailed comparison and exchange mechanism inside loops increases the constant factor.

2) Quicksort could leverage on the locality of reference (and therefore, memory access) advantages provided by the hardware and the operating system

How n log n?

If you choose the pivot right, then, on an average, you get a 1/4, 3/4 split which gives an average running time of 0(n log n)

Source : Goodrich and Tamassia

Pivot Choosing strategy :

There are many methods to choose a pivot

1)  First Item
2)  Last item 
3)  Median
4)  Median of k (generally of 3)
5)  Random item 

Choosing a random key as the pivot is the preferred method because of the guaranteed worst case possibility with the other selection methods with following kinds of sequences :

1)  Presorted list 
        when chosing first item as your pivot in case of natural order
                     last item as your pivot in case of reverse order
2)  Repeated elements   
3)  Unimodal sequences* (when median is chosen as pivot)

Bottom line : When you choose a pivot in such a way that one portion of your split (either I1 or I2) becomes empty AND if you are doing it all through the list, then you are essentially doing the split N times.

Quicksort in Java

package me.rerun;

import java.util.Arrays;

public class QuickSort {

	public static void quickSort (Comparable comparableArray[], int lowIndex, int highIndex){
		
		//at least one item must exist in the array 
		if (lowIndex>=highIndex){
			return;
		}
	
		int pivotIndex=getMedianIndexAsPivotIndex(lowIndex, highIndex);
		//1) Choose pivot from the sublist
		Comparable pivot=comparableArray[pivotIndex];
		System.out.println("Pivot : "+pivot);
		//2) Swap the pivot to the last item in the array
		swapItemsWithIndices(comparableArray, pivotIndex, highIndex); 	
 
		/*	
		  	Get the border indices sandwiching the unsorted items alone (ignore pivot (now, in the highIndex))
			set 'i' to point to the item before the first Index
			set 'j' to point to the item before pivot
			
			Notice that this way, the following invariant gets maintained 
			all through the sorting procedure
			
			a. All items left of Index 'i' have a value <=pivot
			b. All items right of Index 'j' have a value >=pivot
		*/

		int i=lowIndex-1;
		int j=highIndex;
		
		do{ //Notice the <j (pivot item is ignored). We stop when both the counters cross
			
			//compareTo will return 0 when it reaches the pivot - will exit loop
			do {i++;} while (comparableArray[i].compareTo(pivot)<0);
			//we dont have the protection as the previous loop. 
			//So, add extra condition to prevent 'j' from overflowing outside the current sub array
			do {j--;} while (comparableArray[j].compareTo(pivot)>0 &&(j>lowIndex));
			
			if (i<j){
				swapItemsWithIndices(comparableArray, i, j);
			}
			System.out.println("I :"+i + " J :"+j);
		} while (i<j);
		
		swapItemsWithIndices(comparableArray, highIndex, i);//bring pivot to i's position	
		System.out.println("Comparable array : "+Arrays.asList(comparableArray));
		
		//the big subarray is partially sorted (agrees to invariant). Let's recurse and bring in more hands
		
		quickSort(comparableArray, lowIndex, i-1); //sort subarray between low index and one before the pivot
		quickSort(comparableArray, i+1, highIndex); //sort subarray between low index and one before the pivot
	}
	
	
	//... since swapping with array is the easiest way to swap two objects
	private static void swapItemsWithIndices(Comparable[] comparableArray, int firstItem, int secondItem) {
		System.out.println("Swapping "+comparableArray[firstItem] +"  and  "+comparableArray[secondItem]);
		final Comparable tempItem=comparableArray[firstItem];
		comparableArray[firstItem]=comparableArray[secondItem];
		comparableArray[secondItem]=tempItem;
		System.out.println("After swap array : "+Arrays.asList(comparableArray));
	}


	//Variation 1 - chose median as pivot  
	private static int getMedianIndexAsPivotIndex(int lowIndex, int highIndex) {
		return lowIndex+((highIndex-lowIndex)/2);
	}


	

	public static void main(String[] args) {

		//Integer[] unsortedArray=new Integer[]{1,32,121,1424,2,1214,121214,3535,754,343};
		//Integer[] unsortedArray=new Integer[]{4,4,8,0,8,9,7,3,7,6}; 
		Integer[] unsortedArray=new Integer[]{5,5,5,5,5,5,5,5,5,5};
		
		long startTime = System.nanoTime();
		System.out.println("Original array : "+Arrays.asList(unsortedArray));
		quickSort(unsortedArray, 0, unsortedArray.length-1);
		
		System.out.println("Sorted array : "+Arrays.asList(unsortedArray));
		System.out.println(System.nanoTime()-startTime);
	}

}

References

Goodrich and Tamassia
Three Beautiful Quicksorts
Quicksort is Optimal
Unimodal sequences

 

 

 

 

Published at DZone with permission of Arun Manivannan, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Russel Winder replied on Sat, 2012/09/08 - 6:39am

Mergesort? Modified Tim Sort?

Raoul Ohio replied on Sun, 2012/09/09 - 11:06pm

If  you would actually read Goodrich and Tamassia or any other algorithms book, you will find that QuickSort is by no means the fastest sort.

Russel Winder replied on Mon, 2012/09/10 - 3:02am

Raoul,

 It is bizarre how much disinformation gets promulgated via the Web isn't it! It is a great pity more programmers do not read these great books. e.g Cormen et al. 

Arun Manivannan replied on Mon, 2012/09/10 - 7:00am in response to: Russel Winder

Thanks for pointing out the book Russel. This write up and in fact the whole blog is just the summary of my self-learning process on the various algorithms and basics of computer science.  I am sure there are possibilities of mistakes in the process and I would greatly appreciate constructive criticisms.

Arun Manivannan replied on Mon, 2012/09/10 - 7:18am in response to: Raoul Ohio

Thanks Raoul.  By no means Quicksort is the fastest considering the existence of a variety of hybrid sorts or other sorts which knows beforehand about the data.  My bad, I should have updated the content saying that QS is not only the fastest comparison based sort but also "the fastest non-hybrid sort which has no knowledge about the data".  Please go ahead and correct me if I am wrong. You'll just be helping me learn.

 I'll update the source blog with your information. 

Arun Manivannan replied on Mon, 2012/09/10 - 7:16am in response to: Raoul Ohio

Thanks Raoul.  By no means Quicksort is the fastest considering the existence of a variety of hybrid sorts or other sorts which knows beforehand about the data.  My bad, I should have updated the content saying that QS is not only the fastest comparison based sort but also "the fastest non-hybrid sort which has no knowledge about the data".  Please go ahead and correct me if I am wrong. You'll just be helping me learn.

 I'll update the source blog with your information. 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.