Cracking Quick Sort algorithm: From Theory to Practice in Minutes

Quicksort is one of the fastest sorting algorithms. It takes an array of values, chooses one of the values as the 'pivot' element, and moves the other values so that lower values are on the left of the pivot element, and higher values are on the right of it.

Quick Sort stands as one of the most elegant and efficient sorting algorithms in the world of algorithms. Unlike simpler algorithms like Bubble Sort or Selection Sort, Quick Sort employs a sophisticated divide-and-conquer strategy that makes it significantly faster in practice. While Merge Sort also uses divide-and-conquer, Quick Sort's unique partitioning approach often leads to better performance and memory usage.

Average Time Complexity: O(n log n)

Worst Case Time Complexity: O(n²)

Space Complexity: O(log n)

Table of Contents

1. What is quick sort algorithm
2. How does quick sort work
   • Time Complexity
   • Space Complexity
3. JavaScript Implementation
4. Conclusion

What is Quick Sort Algorithm

Quick Sort is a highly efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. Unlike Merge Sort, which divides first and combines later, Quick Sort does its sorting during the partitioning process.

Consider this comparison with other sorting algorithms:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

How does quick sort work?

Before we dive into the JavaScript implementation of quick sort algorithms, let's take a step-by-step approach to understand how the algorithm works by manually sorting a simple array of numbers with just four simple steps.

Quick sort can be broken down into four simple steps:

1. Choose a pivot element from the array. This element could be the first, the last, the middle or even a random element from the list/array.
2. Rearrange the array so that all elements less than the pivot are on the left, and all elements greater are on the right.
3. Swap the pivot element with the first element of the greater values, so that the pivot is in the middle.
4. Recursively apply the same operations to the sub-arrays on the left and right of the pivot.

Let's apply these steps to a real array. Shall we?

Initial Array: [3, 6, 2, 7, 1]

Step 1: Choose a Pivot

• We choose the last element as the pivot for simplicity.
• Pivot = 1

Step 2: Rearrange Array Around Pivot

• Rearrange so that all elements less than the pivot (1) are on the left and all elements greater are on the right.
• As we go through each element:
  • 3 (greater than 1) → stays on the right.
  • 6 (greater than 1) → stays on the right.
  • 2 (greater than 1) → stays on the right.
  • 7 (greater than 1) → stays on the right.
• Rearranged Array: [1, 6, 2, 7, 3]

Step 3: Swap Pivot to its Correct Position

• Swap the pivot (1) with the first element greater than it, which is 6.
• Array after swapping: [1, 3, 2, 7, 6]
• Now, 1 is in the correct position (index 0).

Step 4: Recursive Quick Sort on Sub-arrays

• Left Sub-array: [] (no elements left of 1, so nothing to sort here)
• Right Sub-array: [3, 2, 7, 6]

---

Sorting the Right Sub-array [3, 2, 7, 6] recursively

Step 1: Choose a Pivot

• Pivot = 6 (last element)

Step 2: Rearrange Array Around Pivot

• Arrange elements less than 6 to the left and greater ones to the right:
  • 3 (less than 6) → stays on the left.
  • 2 (less than 6) → stays on the left.
  • 7 (greater than 6) → stays on the right.
• Rearranged Array: [3, 2, 6, 7]

Step 3: Swap Pivot to Its Correct Position

• 6 is already in the correct position (index 2).
• Array: [1, 3, 2, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

• Left Sub-array: [3, 2]
• Right Sub-array: [7] (single element, no sorting needed)

---

Sorting the Left Sub-array [3, 2]

Step 1: Choose a Pivot

• Pivot = 2 (last element)

Step 2: Rearrange Array Around Pivot

• Rearrange so elements less than 2 are on the left:
  • 3 (greater than 2) → stays on the right.
• Rearranged Array: [2, 3]

Step 3: Swap Pivot to Its Correct Position

• 2 is already in the correct position (index 1).
• Array: [1, 2, 3, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

• Left Sub-array: [] (no elements)
• Right Sub-array: [3] (single element, no sorting needed)

---

Final Sorted Array

After sorting all the sub-arrays, we get the final sorted array:

Sorted Array: [1, 2, 3, 6, 7]

Below is the best illustration of how this works in real life:

Time Complexity

Quick Sort's time complexity varies based on pivot selection:

• Best Case (O(n log n)):

  • Occurs when the pivot always divides the array into equal halves
  • Similar to Merge Sort's performance

• Average Case (O(n log n)):

  • Most practical scenarios
  • Better than Merge Sort due to better cache utilization

• Worst Case (O(n²)):

  • Occurs with already sorted arrays and poor pivot selection
  • Can be avoided with good pivot selection strategies

Space Complexity

Quick Sort's space complexity is O(log n) due to:

• Recursive call stack depth
• In-place partitioning (unlike Merge Sort's O(n) extra space)
• Better memory efficiency compared to Merge Sort

JavaScript Implementation

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Conclusion

Quick Sort is a popular choice due to its efficiency and in-place sorting. It outperforms simpler algorithms like Bubble Sort and Selection Sort with its O(n log n) average-case performance and low space complexity.

Key takeaways:

1. Choose pivot selection strategy carefully
2. Consider input characteristics when deciding between Quick Sort and other algorithms
3. Use randomized pivot selection for better average-case performance

---

---

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

Emmanuel Ayinde Follow

Software Engineer | Technical Writer | Backend, Web & Mobile Developer ? | Passionate about crafting efficient and scalable software solutions. #letsconnect ?

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding ?‍??

The above is the detailed content of Cracking Quick Sort algorithm: From Theory to Practice in Minutes. For more information, please follow other related articles on the PHP Chinese website!