JavaScript Program to Implement the Quick Sort Algorithm

Introduction

Quick Sort is a widely used, efficient sorting algorithm based on the divide-and-conquer strategy. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot. The algorithm then recursively sorts the sub-arrays. This guide will walk you through writing a JavaScript program to implement the Quick Sort algorithm.

Problem Statement

Create a JavaScript program that:

• Sorts an array of integers using the Quick Sort algorithm.
• Displays the sorted array.

Example:

• Input: [10, 7, 8, 9, 1, 5]

• Output: [1, 5, 7, 8, 9, 10]

• Input: [50, 40, 30, 20, 10]

• Output: [10, 20, 30, 40, 50]

Solution Steps

1. Choose a Pivot: Select a pivot element from the array.
2. Partition the Array: Re-arrange elements such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right.
3. Recursively Sort Sub-arrays: Apply the same logic to the sub-arrays formed after partitioning.
4. Base Case: Recursion ends when the array has one or zero elements.

JavaScript Program

// JavaScript Program to Implement Quick Sort Algorithm
// Author: https://www.rameshfadatare.com/

// Step 1: Define the quickSort function
function quickSort(arr) {
    // Step 2: Base case for recursion
    if (arr.length <= 1) {
        return arr;
    }

    // Step 3: Select the pivot (using the middle element)
    const pivot = arr[Math.floor(arr.length / 2)];

    // Step 4: Partition the array into left and right sub-arrays
    const left = [];
    const right = [];

    // Step 5: Partition the array by comparing elements to the pivot
    arr.forEach((element) => {
        if (element < pivot) {
            left.push(element);
        } else if (element > pivot) {
            right.push(element);
        }
    });

    // Step 6: Recursively sort the left and right sub-arrays, then concatenate
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Example usage
const arr = [10, 7, 8, 9, 1, 5];
console.log("Original Array:", arr);
const sortedArray = quickSort(arr);
console.log("Sorted Array:", sortedArray);

Explanation

Step 1: Define the quickSort Function

• The function takes an array arr as input and returns a sorted version of the array using Quick Sort.

Step 2: Base Case for Recursion

• The base case for recursion is when the array has one or zero elements. In this case, the array is already sorted, so it is returned as is.

Step 3: Select the Pivot

• The pivot is chosen as the middle element of the array (arr[Math.floor(arr.length / 2)]). This is one possible approach, but other elements (e.g., the first or last element) can also be chosen as the pivot.

Step 4: Partition the Array

• Two empty arrays, left and right, are created to store elements smaller and greater than the pivot, respectively.

Step 5: Partition by Comparing Elements to the Pivot

• Each element in the array is compared with the pivot:
  • If it's smaller than the pivot, it goes into the left array.
  • If it's greater than the pivot, it goes into the right array.

Step 6: Recursively Sort and Concatenate

• The quickSort function is called recursively on the left and right arrays, and the sorted results are concatenated with the pivot in between. The concatenated array is returned as the sorted array.

Output Example

Original Array: [10, 7, 8, 9, 1, 5]
Sorted Array: [1, 5, 7, 8, 9, 10]

Example with Different Input

const arr = [50, 40, 30, 20, 10];
console.log("Original Array:", arr);
const sortedArray = quickSort(arr);
console.log("Sorted Array:", sortedArray);

Output:

Original Array: [50, 40, 30, 20, 10]
Sorted Array: [10, 20, 30, 40, 50]

Time Complexity

• Best Case: O(n log n) when the pivot splits the array into two equal halves.
• Worst Case: O(n²) when the pivot is the smallest or largest element, leading to unbalanced partitions.
• Average Case: O(n log n).

Conclusion

This JavaScript program demonstrates how to implement the Quick Sort algorithm using recursion and partitioning. By leveraging the divide-and-conquer approach, the program efficiently sorts arrays in O(n log n) time on average. Understanding Quick Sort is essential for learning how to optimize sorting operations and implement efficient algorithms.