QuickSort algorithm in JavaScript

QuickSort is a divide-and-conquer sorting algorithm that works by selecting a “pivot” element from the array, partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot, and then repeating the process recursively on the sub-arrays. The end result is that the elements of the array are rearranged such that they are in order. This algorithm has an average time complexity of O(n log n), making it one of the fastest sorting algorithms available.

The QuickSort algorithm works as follows:

1. Choose a pivot element from the array.
2. Partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
3. Recursively sort the sub-arrays.
4. Combine the sorted sub-arrays and the pivot element to obtain the fully sorted array.

The pivot element acts as a dividing point, allowing the algorithm to break the problem down into smaller sub-problems that can be solved recursively. By repeating this process, the elements in the array are eventually rearranged into the correct order.

Here’s an implementation of the QuickSort algorithm in JavaScript:

// Main quickSort function
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

// Pivot helper function
function pivot(arr, start = 0, end = arr.length - 1) {
  let pivot = arr[start];
  let swapIndex = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }

  [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]];
  return swapIndex;
}

The quickSort function is the main driver of the QuickSort algorithm. It takes an array arr as input and uses optional arguments left and right to specify the start and end indices of the portion of the array to be sorted. The function returns the fully sorted array.

quickSort function:

// Main quickSort function
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

• Input: an array arr, and optional start index left and end index right
• Output: a sorted array
• The function first checks if left is less than right. If this is not the case, the portion of the array being considered is already fully sorted and the function returns arr.
• If left is less than right, the function calls the pivot helper function to determine the pivot index.
• The function then calls itself recursively on the portion of the array to the left and right of the pivot to sort both sub-arrays.
• The final result is a fully sorted arr.

pivot function:

// Pivot helper function
function pivot(arr, start = 0, end = arr.length - 1) {
  let pivot = arr[start];
  let swapIndex = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }

  [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]];
  return swapIndex;
}

• Input: an array arr, and optional start index start and end index end
• Output: the pivot index
• The function selects the first element of the portion of the array being considered as the pivot.
• A loop is used to place all elements smaller than the pivot to its left and all elements larger to its right.
• The final step of the function is to swap the pivot with the final position of the swap index.
• The pivot index is returned.

There are several algorithms that are similar to QuickSort in terms of their approach to sorting an array:

• MergeSort: This is a divide-and-conquer algorithm that splits the array into two halves, sorts each half recursively, and then merges the two sorted halves back together.
• HeapSort: This is an in-place comparison-based sorting algorithm that uses a binary heap data structure to sort the array.
• BubbleSort: This is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
• InsertionSort: This is a simple comparison-based sorting algorithm that builds the final sorted array one item at a time.

All of these algorithms have their own strengths and weaknesses, and the choice of which one to use depends on the specific requirements of the task at hand.