QuickSort Implementation in Java

Quicksort

Quicksort is an efficient sorting algorithm, which is using divide and conquer algorithm. Quicksort is much more efficient than quadratic sorting algorithms like Bubble Sort and Insertion Sort. Using the divide and conquer approach, the algorithm first divides a large list into two smaller sub-lists using a pivot. The sub-list consists of : the low elements and the high elements. Quicksort is then called recursively to sort the sub-lists.

How Quicksort Works

Steps to implement Quick sort:

• 1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.
• 2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
• 3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Quicksort Complexity

The complexity of quick sort in the average case is O(n log(n)) and in the worst case is O(n2). The algorithm is extremely efficient if the pivot is properly chosen. If the pivot is always the middle element, then the algorithm will be O(nlogn). The n because we have to do n-1 comparisons and the long n because we have to divide the array log n times. however, in the worst case, this algorithm can be o(n2). This is usually the case if, at each iteration, the pivot happens to be the smallest or largest element in the array. Then you have to break down the list n times and do n-1 comparisons every time.

Quicksort Algorithm

Below is an example of Quicksort written in Java..

package miftyisbored;

public class MiftyQuickSort {
	   /**
	   * This main method is used to illustrate how to use the Quicksort Algorithm
	   **/
	   public static void main(String[ ] args)
	   {
	      final String BLANK_SPACE = "  "; // Just because I am lazy ...
	      int[ ] data = { 10000, 1002, 83, 12, 58, 72, 66, 65, 75648, 90, 23, 37, 41, 66, 0, 3100, 55555, 1, 67 };

	      // Print the array before sorting:
	      System.out.println("Welcome to Mifty's Quicksorter");
	      System.out.println("Here is the original unsorted list:");
	      for (int i = 0; i < data.length; i++)
	         System.out.print(data[i] + BLANK_SPACE);
	      System.out.println( );

	      // Sort the numbers, and print the results
	      quickSort(data,0,data.length-1);
	      
	      // print the results
	      System.out.println("All numbers are sorted now!");
	      System.out.println("Here is the ordered list:");
	      for (int i = 0; i < data.length; i++)
	         System.out.print(data[i] + BLANK_SPACE);
	      System.out.println( );
	   }
	   
	   /**
	    * This function sorts an array of integers from smallest to largest using quick sort
	    * @param: data - the array to be sorted
	    * @param: startIndex - the starting index
	    * @param: endIndex - the ending index
	    */
	   public static void quickSort(int[] data, int startIndex, int endIndex)
	   {
	        if(startIndex < endIndex)
	        {
	            int partitionIndex = partition(data,startIndex,endIndex);
	            quickSort(data, startIndex, partitionIndex-1);
	            quickSort(data, partitionIndex+1, endIndex);
	        }
	    }
	   
	   /*
	    * This function returns the pivot after partitioning an array in 2
	    * @param: data - the array to be sorted
	    * @param: startIndex - the starting index
	    * @param: endIndex - the ending index
	    */
	   private static int partition(int[] data, int startIndex, int endIndex) {
		   // take pivot to be the last element of the array and the partition index to be the first index
		   int currentPivot = data[endIndex];
		   int partitionIndex = startIndex;
		   
		   // loop and swap so that we can determine the final positionof the pivot element
		   for(int i = startIndex; i < endIndex; i++){
			   if(data[i] <= currentPivot){
				   swap(data,i,partitionIndex);
				   partitionIndex++;
			   }
		   }
		   
		   // at this point, all elements smaller than pivot are before the partition index
		   // and elements larger or equal to the pivot are after the partition index
		   // finally, swap the element at end index with the element at the partition index since that is its
		   // final place
		   swap(data,partitionIndex,endIndex);
		   
		   return partitionIndex;
	   }
	   
	   /*
	    * This function swaps the values at the provided indixes in the array
	    * @param: data - the array
	    * @param: a - the first index
	    * @param: b - the secong index
	    */
	   private static void swap(int[] data, int a, int b) {
		   int temp = data[a];
       	   data[a] = data[b];
       	   data[b] = temp;
	   }
}

The following is the output of the application

Welcome to Mifty's Quicksorter
Here is the original unsorted list:
10000  1002  83  12  58  72  66  65  75648  90  23  37  41  66  0  3100  55555  1  67  
All numbers are sorted now!
Here is the ordered list:
0  1  12  23  37  41  58  65  66  66  67  72  83  90  1002  3100  10000  55555  75648