What Is the Quick Sort Algorithm?
Quick Sort is a highly efficient and widely used sorting algorithm that was developed by Tony Hoare in 1960. Its performance and ease of implementation makes it a popular sorting algorithm.
Quick Sort use the divide-and-conquer strategy to organize elements in an array or list, and it operates in-place, meaning it requires only a small, constant amount of additional memory.
Characteristics of Quick Sort:
1. Divide and Conquer Strategy
The divide-and-conquer strategy is at the heart of Quick Sort’s efficiency. It breaks down a problem into smaller subproblems, and solves each subproblem independently, and then combines their solutions to solve the original problem. In the context of Quick Sort, the array is divided into smaller subarrays, which are then sorted recursively.
2. In-place Sorting
Quick Sort is an in-place sorting algorithm, which means it rearranges the elements of the array within the original array itself without needing extra space proportional to the input size. This makes Quick Sort space-efficient compared to other sorting algorithms like Merge Sort, which requires additional memory for merging.
3. Recursive Algorithm
Quick Sort is inherently recursive. It repeatedly partitions the array into smaller subarrays around a pivot element and then recursively sorts these subarrays. This recursion continues until the base case is reached, where the subarrays have 0 or 1 element and are therefore already sorted.
How Quick Sort Works
To understand how Quick Sort works, it’s essential to break down its key steps:
1. Choosing a Pivot: The first step in Quick Sort is to select a pivot element from the array. The pivot element can be chosen in several ways, including:
- The first element
- The last element
- A random element
- The median of the first, middle, and last elements (median-of-three)
The choice of the pivot can affect the algorithm’s performance, but for simplicity, we often choose the last element as the pivot.
2. Partitioning the Array: After choosing the pivot, the next step is to partition the array into two subarrays:
- Elements less than the pivot
- Elements greater than or equal to the pivot
During the partitioning process, elements are rearranged so that all elements less than the pivot come before the pivot, and all elements greater than or equal to the pivot come after it. The pivot element is then in its correct sorted position.
3. Recursively Sorting Subarrays: Once the array is partitioned, Quick Sort recursively applies the same steps to the left and right subarrays:
- The left subarray contains elements less than the pivot.
- The right subarray contains elements greater than or equal to the pivot.
The recursion continues until the base case is reached, where subarrays have 0 or 1 element and are therefore already sorted.
Implementing Quick Sort Algorithm With JavaScript
Here we will discuss how to implement Quick Sort algorithm in JavaScript:
function quickSort(arr) {
// Base case: arrays with 0 or 1 element are already sorted
if (arr.length <= 1) {
return arr;
}
// Choose a pivot element (here, the last element)
let pivot = arr[arr.length - 1];
let left = [];
let right = [];
// Partition the array into two subarrays
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 subarrays and concatenate them with the pivot
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Example usage:
let array = [3, 6, 8, 10, 1, 2, 1];
let sortedArray = quickSort(array);
console.log(sortedArray); // Output: [1, 1, 2, 3, 6, 8, 10]Step by Step Code Implementation
Step 1: Base Case
First, define the base case for the recursion. If the array has 0 or 1 element, it is already sorted, so return the array as is.
if (arr.length <= 1) {
return arr;
}Step 2: Choosing the Pivot
Next, choose the pivot element. In this example, we choose the last element of the array as the pivot.
let pivot = arr[arr.length - 1];Step 3: Partitioning the Array
Create two empty arrays, ‘left‘ and ‘right‘, iterate through the array (excluding the pivot) and push elements less than the pivot into the ‘left‘ array and elements greater than or equal to the pivot into the ‘right‘ array.
let left = [];
let right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}Step 4: Recursively Sorting the Subarrays
Recursively apply Quick Sort to the ‘left‘ and ‘right‘ arrays. Finally, concatenate the sorted ‘left‘ array, the pivot, and the sorted ‘right‘ array to get the final sorted array.
return [...quickSort(left), pivot, ...quickSort(right)];Testing the Quick Sort Algorithm
To ensure the Quick Sort implementation works correctly, test it with various input arrays.
console.log(quickSort([5, 3, 8, 4, 2])); // Output: [2, 3, 4, 5, 8]
console.log(quickSort([15, 10, 20, 30, 5])); // Output: [5, 10, 15, 20, 30]
console.log(quickSort([1, 2, 3, 4, 5])); // Output: [1, 2, 3, 4, 5]
console.log(quickSort([10, -1, 2, 5, 0, 6, 4, -5])); // Output: [-5, -1, 0, 2, 4, 5, 6, 10]Optimizing Quick Sort
While the basic implementation of Quick Sort is efficient, there are several optimizations that can further improve its performance:
1. Choosing a Better Pivot
Choosing a good pivot is crucial for the performance of Quick Sort. Use the median of three (first, middle, and last elements) as the pivot.
function medianOfThree(arr, low, high) {
let mid = Math.floor((low + high) / 2);
let a = arr[low];
let b = arr[mid];
let c = arr[high];
if ((a - b) * (c - a) >= 0) return a;
else if ((b - a) * (c - b) >= 0) return b;
else return c;
}2. In-place Partitioning
Using additional arrays (left and right) increases the space complexity. An in-place partitioning scheme, like Lomuto’s or Hoare’s partitioning, can reduce space complexity.
Here’s an implementation using Lomuto’s partitioning scheme:
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
let pivotIndex = partition(arr, low, high);
quickSortInPlace(arr, low, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, high);
}
return arr;
}
function partition(arr, low, high) {
let pivot = arr[high];
let i = low;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[high]] = [arr[high], arr[i]];
return i;
}
// Example usage:
let array = [3, 6, 8, 10, 1, 2, 1];
let sortedArray = quickSortInPlace(array);
console.log(sortedArray); // Output: [1, 1, 2, 3, 6, 8, 10]Real-world Applications of Quick Sort
Quick Sort is widely used in various real-world applications due to its efficiency and simplicity:
- Search Engines: Search engines use Quick Sort to sort and index web pages efficiently, enabling quick retrieval of relevant search results.
- Database Management: Databases use Quick Sort for sorting records and optimizing query performance, especially for large datasets.
- Computer Graphics: In computer graphics, Quick Sort is used for depth-sorting algorithms to render scenes correctly.
Wrap Up
In this guide, we just covered the fundamental concepts of Quick Sort, step-by-step implementation in JavaScript, and optimizations.
Feel free to experiment with different pivot selections and partitioning schemes to see how they affect the performance of Quick Sort in various scenarios. Happy coding!
Also Read:
