JavaScript: Implement the Quick Sort Algorithm

1. Introduction

QuickSort is a divide-and-conquer sorting algorithm. It 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. The sub-arrays are then sorted recursively. QuickSort is often faster in practice than other O(n²) algorithms such as Bubble Sort.

2. Program Overview

For this guide, we will:

1. Initialize an array of numbers.

2. Implement the Quick Sort algorithm.

3. Display the sorted array.

3. Code Program

let numbers = [10, 80, 30, 90, 40, 50, 70];  // Initializing an unsorted array

function quickSort(arr, low, high) {
    if (low < high) {
        let pi = partition(arr, low, high);  // Partitioning index

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high);  // After pi
    }
}

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = (low - 1);  // Index of smaller element

    for (let j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    // Swap arr[i + 1] and arr[high] (or pivot)
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

    return (i + 1);
}

quickSort(numbers, 0, numbers.length - 1);  // Sorting the array using QuickSort

console.log("Sorted array:", numbers);

Output:

Sorted array: [10, 30, 40, 50, 70, 80, 90]

4. Step By Step Explanation

1. Array Initialization: We start with an unsorted array named numbers.

2. QuickSort Implementation:

- quickSort(): This is a recursive function that sorts the elements before and after the partitioning index.

- partition(): This function takes the last element as the pivot, places it at its correct position, and places all smaller elements to its left and larger elements to its right.

3. Process Inside partition():

- We start from the first element and check if the current element is smaller than the pivot. If it is, we increase the index of the smaller element and swap the current element with the element at the smaller index.

- Once we've gone through the entire array, we swap the pivot element with the element next to the smaller index. This places the pivot in its correct sorted place.

4. Displaying the Result: After sorting the array using the quickSort function, we display the sorted array.