05. Quick Sort

Quick sort is a divide-and-conquer algorithm developed by Tony Hoare in 1959. Let's look at how Quick Sort works.

Algorithm Pseudocode

Assign the last element as a pivot.
Place a line to partition the array into two, starting from the far left end of the array.
For each element in our array that is less than or equal to the pivot, swap it with the element to the right of the wall and move wall up one.
Place pivot as the first element on the right of the partitioning wall.
Split and repeat, then merge together for sorted array.

Here's a step-by-step illustration of what is going on. Try writing down the array [8, 4, 7, 2, 9, 5] and running through Quick Sort yourself.

Visualization

Here's a nifty animation for your better learning experience.

Characteristics

Quick sort is said to be similar to insertion and bubble, but more efficient in most cases. Depending on the implementation, it may or may not be a stable sort.

Complexity

O(n²) at worst case, and O(n log n) on average. O(n) space for recursion stack.

Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

import java.util.Arrays;
 
public class QuickSort extends Sort {
 
  public static void main(String[] args) {
 
    int[] testInt = {1,6,2,3,6,7,4,2,5};
 
    quickSort(testInt, 0, testInt.length-1);
    System.out.println(Arrays.toString(testInt));
  }
 
  public static void quickSort(int[] input, int low, int high) {
 
    // Base case
    if (low >= high) {
      return;
    }
 
    // Use last element as pivot
    int pivot = input[high];
    // Set our wall at the first element
    int wall = low;
 
    /**
     * Iterate through array - if current element is less that or equal 
     * to pivot, swap with element above wall
     */
    for (int i = low; i < high; i++) {
      if (input[i] <= pivot) {
        swap(input, i, wall++);
      }
    }
 
    // Place pivot to right to just right of wall
    swap(input, wall, high);
 
    // Recursively call for each part of array
    quickSort(input, low, wall-1);
    quickSort(input, wall, high);
 
  }
 
}

References

04. Insertion Sort

Aching back from coding all day?

Acupressure Mat & Pillow

Relieve your stress, back, neck and sciatic pain through 1,782 acupuncture points for immediate neck pain relief. Made for lower, upper and mid chronic back pain treatment, and improves circulation, sleep, digestion and quality of life.

$$ Check price
Amazon 4.5 logo

(1,890+ reviews)

Ace your Technical Interview

Programming Interviews: Exposed

In today's tight job market, competition for programming jobs is hotter than ever. This third edition of a popular guide to programming interviews includes new code examples, information on the latest languages, new chapters on sorting and design patterns, tips on using LinkedIn, and a downloadable app to help prepare applicants for the interview.

$ Check price
Amazon 4.5 logo

(94+ reviews)

More Algorithms resources