Quick Sort Implementation in Java

Quick Sort

Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.
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 to the sub-list of elements with greater values.

Quick Sort Example - GIF Format

Quick Sort in Java

public class QuickSort {  
      private int[] numbers;  
      public void sort(int[] values) {  
           // check for empty or null array
           if (values == null || values.length == 0) {  
                return;  
           }  
           this.numbers = values;  
           quicksort(0, values.length - 1);  
      }  
      private void quicksort(int low, int high) {  
           int i = low;  
           int j = high;  
           // Get the pivot element from the middle of the list
           int pivot = numbers[low + (high - low) / 2];
           // Divide into two lists  
           while (i <= j) {  
                // If the current value from the left list is smaller then the pivot
                // element then get the next element from the left list
                while (numbers[i] < pivot) {  
                     i++;  
                }  
                // If the current value from the right list is larger then the pivot
                // element then get the next element from the right list
                while (numbers[j] > pivot) {  
                     j--;  
                }  
                // If we have found a values in the left list which is larger then
                // the pivot element and if we have found a value in the right list
                // which is smaller then the pivot element then we exchange the
                // values.
                // As we are done we can increase i and j
                if (i <= j) {  
                     exchange(i, j);  
                     i++;  
                     j--;  
                }  
           }  
           if (low < j) {  
                quicksort(low, j);  
           }  
           if (i < high) {  
                quicksort(i, high);  
           }  
      }  
      private void exchange(int i, int j) {  
           int temp = numbers[i];  
           numbers[i] = numbers[j];  
           numbers[j] = temp;  
      }  
      public static void main(String[] args) {  
           int[] numbers = { 84, 90, 69, 76, 86, 94, 75, 91 };  
           print("Before: ", numbers);  
           QuickSort quickSort = new QuickSort();  
           quickSort.sort(numbers);  
           print("After: ", numbers);  
      }  
      public static void print(String label, int[] numbers) {  
           System.out.print(label + ": ");  
           for (int i : numbers) {  
                System.out.print(i + " ");  
           }  
           System.out.println();  
      }  
 }  

Complexity Analysis

Quick Sort Complexity

Case	Complexity
Worst case performance	O(n^2)
Best case performance	O(n log n)
Average case performance	O(n log n)

References

Quick Sort from Wikipedia
Quicksort in Java - Tutorial by Lars Vogel