Quick Sort in JavaScript

When it comes to sorting large datasets in JavaScript, having an efficient algorithm is crucial. Quick Sort, a popular sorting algorithm, offers a fast and reliable solution. Developed by Tony Hoare, Quick Sort follows a divide-and-conquer approach to efficiently sort arrays. This article will delve into the Quick Sort algorithm and provide a step-by-step guide to implementing it in JavaScript.

Quick Sort Algorithm

Quick Sort is based on the concept of partitioning. The algorithm selects a pivot element from the array and partitions the array into two sub-arrays, one with elements smaller than the pivot and the other with elements larger than the pivot. It then recursively applies the same process to the sub-arrays until the entire array is sorted.

Quick Sort Implementation in JavaScript

To implement Quick Sort in JavaScript, we will define a function called quickSort that takes an array as a parameter.

function swap(arr, leftIndex, rightIndex) {
    const temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;
}

function partition(arr, low, high) {
    const pivot = arr[Math.floor((low + high) / 2)];
    let i = low;
    let j = high;

    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(arr, low, high) {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex, high);
    }
    return arr;
}

// Usage example:
const array = [64, 25, 12, 22, 11];
const sortedArray = quickSort(array, 0, array.length - 1);
console.log("Sorted array: " + sortedArray);

Explanation of the Code:*

• The swap function is a utility function used to swap two elements in the array.
• The partition function selects a pivot element from the array (in this case, the middle element) and rearranges the array, placing elements smaller than the pivot on its left and elements larger on its right. It returns the index of the pivot element.
• The quickSort function recursively calls itself to sort the sub-arrays. It uses the partition function to divide the array into sub-arrays and sort them individually.
• In the usage example, we initialize an array and call quickSort with the array, starting index 0, and ending index array.length – 1.
• Finally, we print the sorted array using console.log().

Quick Sort is a powerful and efficient algorithm for sorting arrays in JavaScript. By understanding its divide-and-conquer approach and following the step-by-step implementation provided in this article, you now have the knowledge to utilize Quick Sort in your JavaScript projects. Its speed and reliability make it an excellent choice for sorting large datasets. Give it a try and experience the benefits of Quick Sort in your own code.

• Quick Sort in C++
• Quick Sort in Java