•
4 min read

Quick Sort: The Lightning Fast Sorting Algorithm

Quick Sort - “Divide and Conquer” in Sorting

Quick Sort is a “lightning-fast” and extremely efficient sorting algorithm. It is one of the most widely used algorithms today, especially in applications that require handling large amounts of data. Quick Sort is based on the “divide and conquer” principle – a powerful strategy that helps solve complex problems by breaking them down into smaller, simpler subproblems, solving each subproblem, and then combining them to obtain the final result.

How Does Quick Sort Work?

Basically, Quick Sort works as follows:

  1. Choose a “Pivot”: First, the algorithm selects an element in the array to be the “pivot.”
  2. Partitioning: Next, the remaining elements in the array are divided into two groups:
    • Group 1: Contains elements smaller than the pivot.
    • Group 2: Contains elements greater than or equal to the pivot.
  3. Recursion: The algorithm repeats the process (choosing a pivot and partitioning) for each group (group 1 and group 2) recursively until each group contains only one element or no elements at all. At that point, the array is sorted.

Implementing Quick Sort in JavaScript

To understand better, let’s look at how to implement Quick Sort in JavaScript:

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; // If the array has 0 or 1 element, it is already sorted
  }

  const pivot = arr[arr.length - 1]; // Choose the last element as the pivot (could choose another element)
  const left = []; // Sub-array containing elements smaller than the pivot
  const right = []; // Sub-array containing elements greater than or equal to the pivot

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // Recursively sort the sub-arrays and concatenate them with the pivot in between
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Test
const array = [7, 2, 1, 6, 8, 5, 3, 4];
const sortedArray = quickSort(array);
console.log(sortedArray); // Result: [1, 2, 3, 4, 5, 6, 7, 8]

Code Explanation:

  • The quickSort(arr) function takes an array arr that needs to be sorted.
  • If the array has 0 or 1 elements, it is already sorted, so return it.
  • The last element of the array is chosen as the pivot.
  • Two sub-arrays, left and right, are created to store elements smaller than and greater than or equal to the pivot, respectively.
  • A for loop is used to iterate through the array (excluding the pivot) and place each element into either left or right.
  • The function recursively calls quickSort on left and right, and then concatenates the results with the pivot in the middle using the spread syntax ....

Customization and Application

With the above implementation, you can now sort arrays of integers in ascending order. However, you can easily modify the code to sort in descending order or to sort objects based on a specific property.

Conclusion:

Quick Sort is a powerful tool that every programmer should know. With an average time complexity of O(n log n), Quick Sort is well-suited for applications that handle large amounts of data. I hope this article helped you understand the Quick Sort algorithm and how to implement it in JavaScript. Try applying it to your projects and optimize your sorting performance!

P.S. You can also practice with the Javascript Quick Sort solution :<