Quick sort algorithm JavaScript

The Quick Sort algorithm is a widely used sorting algorithm that employs a divide-and-conquer approach. To implement Quick Sort in JavaScript you can recursively partition an array based on a pivot element. It places smaller elements on the left and larger elements on the right, ultimately resulting in a sorted array.

Here are the step-by-step explanations of the Quick Sort algorithm in JavaScript:

1. Choose a pivot element: Select a pivot element from the array. In this example, the pivot is chosen as the last element of the array.
2. Partition the array: Create two empty arrays, left and right, to hold elements smaller than and larger than the pivot, respectively. Iterate through the array (except for the pivot element) and compare each element to the pivot. If an element is smaller than the pivot, add it to the left array; otherwise, add it to the right array.
3. Recursively sort the sub-arrays: Apply the Quick Sort algorithm recursively to the left and right sub-arrays. This step involves calling the quickSort function on the left array and on the right array.
4. Concatenate the sorted sub-arrays: After the recursive sorting, concatenate the sorted left sub-array, the pivot element, and the sorted right sub-array. This step produces the final sorted array.
5. Return the sorted array: Return the sorted array as the output of the quickSort function.

Quick sort algorithm JavaScript example

Simple example code.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

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

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Example usage:
const array = [8, 3, 1, 5, 2, 10, 7, 9];
const sortedArray = quickSort(array);
console.log(sortedArray);

Output:

Here’s an example to illustrate the steps:

// Initial array: [8, 3, 1, 5, 2, 10, 7, 9]
// Pivot: 9

// Partitioning:
// Left array: [8, 3, 1, 5, 2, 7]
// Right array: [10]

// Recursively sort the sub-arrays:
// Left array: [1, 2, 3, 5, 7, 8]
// Right array: [10]

// Concatenating the sorted sub-arrays:
// [1, 2, 3, 5, 7, 8] + [9] + [10] = [1, 2, 3, 5, 7, 8, 9, 10]

// Final sorted array: [1, 2, 3, 5, 7, 8, 9, 10]

By following these steps recursively, the Quick Sort algorithm sorts the array in ascending order.

Space Complexity: The space complexity of Quick Sort is O(log n) on average, where n is the number of elements in the input array.

Time Complexity: The time complexity of Quick Sort is O(n log n) on average, where n is the number of elements in the input array.

Comment if you have any doubts or suggestions on this JS sorting algorithm topic.

Note: The All JS Examples codes are tested on the Firefox browser and the Chrome browser.

OS: Windows 10

Code: HTML 5 Version