Introduction to Quick Sort Algorithm

Click Here to view videos related to this article.
- X
Quick Sort Algorithm Walkthrough
🔗
Quick Sort Algorithmic Dance
🔗
Quick Sort Partitioning
🔗
Click here to suggest a better video or view suggestions..

Imagine you have a big collection of books, and you need to arrange them alphabetically by title. One way of doing this is by randomly selecting a book, putting all the books with titles that come before the selected book on one side, and all the books with titles that come after it on the other side. Then, you’d repeat the process with each smaller pile until all the books are in order. That’s the basic idea behind quick sort, a widely used sorting algorithm in computer science. In this article, we’ll understand quick sort algorithm in a simple, beginner-friendly way. Let’s understand what sorting means before we dive into quick sort algorithm.

What is Sorting?

Sorting is the process of arranging items in a specific order, typically in ascending or descending order. It’s a fundamental operation in computer science that we encounter daily, often without even realizing it!

For example, think about your everyday interactions with organized information. Whether you’re scrolling through your phone or shopping online, sorting plays a crucial role in making information accessible and meaningful. Here are some common examples you probably use regularly where sorting is applied:

  • Names in a contact list (alphabetical order)
  • Prices of products (lowest to highest)
  • Dates in a calendar (chronological order)
  • Test scores (highest to lowest)

When we sort data, we’re essentially organizing it in a way that makes it easier to search, analyze, and visualize. Whether you’re looking for a specific phone number in your contacts or finding the highest score in a game, sorting makes these tasks much more efficient.

What is Quick Sort?

Quick sort is a popular and efficient sorting algorithm that follows a “divide and conquer” strategy. It works by picking an element, called a “pivot,” and rearranging the other elements in the array so that all elements less than the pivot come before it and all elements greater than the pivot come after it. Then recursively repeats this process for elements before and after the pivot.

Here’s the basic algorithm for quick sort:

  1. Select a pivot: Choose one element from the array (called the “pivot”)
  2. Partition: Rearrange the array so that:
    • All elements less than the pivot come before it
    • All elements greater than the pivot come after it
    • The pivot is now in its final sorted position
  3. Recurse: Apply the same process recursively to the sub-arrays on either side of the pivot

How Quick Sort Works: A Simple Analogy

Imagine you’re a teacher and you need to sort exam papers based on student ID. The exam papers with smaller student ID should come first before a paper with higher student ID. Here’s a quick sort way to do it:

  1. Pick a paper at random (the pivot): Let’s say it’s student ID 50.
  2. Divide the papers:
    • Put all papers with IDs less than 50 in one pile.
    • Put all papers with IDs greater than 50 in another pile.
  3. Repeat: Now, do the same thing with each of the smaller piles:
    • Pick a pivot in the “less than 50” pile and divide it.
    • Pick a pivot in the “greater than 50” pile and divide it.
  4. Keep going: Keep repeating this process until each pile has only one paper (or is empty). At this point, everything is sorted!

This is essentially how quick sort works. It’s like repeatedly splitting a problem into smaller, more manageable parts until they’re easy to solve.

Example Walkthrough

Let’s walk through a simple example using the array [5, 2, 8, 1, 9, 4, 7, 3, 6].

  1. Choose a pivot: Let’s pick the middle element, 4, as our pivot.
  2. Partition: Rearrange the array so that:
    • Elements less than 4 come before it.
    • Elements greater than 4 come after it.
    • After partitioning, our array might look like this: [2, 1, 3, 4, 9, 5, 7, 8, 6] (Note: The exact order within the “less than” and “greater than” groups doesn’t matter at this stage).
  3. Recursive calls: Now, we apply quick sort to the two sub-arrays:
    • Sort the “less than 4” part: [2, 1, 3]
    • Sort the “greater than 4” part: [9, 5, 7, 8, 6]
  4. Repeat: We keep applying the same process (choose a pivot, partition, sort sub-arrays) until each sub-array contains only one element (or is empty).
  5. Combine: Since each small part is now sorted, and they’re in the correct order relative to each other, the entire array is sorted!

For a clearer step by step explanation, refer to this article: How Quick Sort Works: Step-by-Step Explanation

Key Characteristics of Quick Sort

  • Divide and Conquer: Quick Sort breaks down the problem into smaller, more manageable subproblems, making it easier to solve.
  • Recursive: The algorithm calls itself on smaller portions of the array until a base case is reached (usually an array with one or zero elements).
  • In-place: Quick Sort doesn’t require a lot of extra memory. It mainly rearranges elements within the original array.
  • Not Stable: When quick sort encounters equal elements, it might not maintain their relative positions in the final sorted array.
  • Pivot Choice: The selection of the pivot can significantly impact the performance of Quick Sort.

What’s Next?

Now that you have a basic understanding of quick sort, you might want to: