QuickSort in JavaScript

Like Merge Sort, QuickSort uses a divide-and-conquer strategy. It selects an element as a pivot and partitions the specified array around it.

There are several different QuickSort variations, and they all select pivots differently.

QuickSort in JavaScript

A partition is the main process of quickSort(). Given an array and an array member x as the pivot, the goal of partitioning is to place x in its correct position in a sorted array and to place all smaller elements before x and all greater elements after x; all of this should be completed in linear time.

JavaScript has the sort() method. Though sort() gives the desired result, the issue is how it sorts the array components.

The default sort() in JavaScript utilizes Insertion Sort from Chrome’s V8 Engine and Merge Sort from Mozilla Firefox and Safari. However, this is not appropriate if you need to sort many items.

As a result, the solution for large datasets is to use Quick Sort.

Here are the simple steps to implement Quick Sort.

Let’s take a closer look at these processes by using an example of an array with unsorted items [9, 1, 4, 7, 0, 2, 5, 8]. We’ll make the last element the pivot.

JavaScript Code for Partitioning:

const partitionFunction = (arratItems, left, right) => {
  let pivotElement = arratItems[Math.floor((right + left) / 2)];
  let leftElement = left;
  let rightElement = right;
  while (leftElement <= rightElement) {
    while (arratItems[leftElement] < pivotElement) {
      leftElement++;
    }
    while (arratItems[rightElement] > pivotElement) {
      rightElement--;
    }
    if (leftElement <= rightElement) {
      swapFunction(arratItems, leftElement, rightElement);
      leftElement++;
      rightElement--;
    }
  }
  return leftElement;
};

JavaScript Code to Carry Out the Swapping:

const swapFunction = (arratItems, leftIndex, rightIndex) => {
  const temp = arratItems[leftIndex];
  arratItems[leftIndex] = arratItems[rightIndex];
  arratItems[rightIndex] = temp;
};

Quick sort is used until all elements in the left, and right arrays have been sorted. No new arrays are created during quick sort; it simply uses the current array.

Therefore, we must call the partitionFunction() function described above to divide the array into pieces. The code is provided here for your use.

const arratItems = [9, 1, 4, 7, 0, 2, 5, 8];
const quickSortFunction = (arratItems, left, right) => {
  let index;
  if (arratItems.length > 1) {
    index = partitionFunction(arratItems, left, right);
    if (left < index - 1) {
      quickSortFunction(arratItems, left, index - 1);
    }
    if (index < right) {
      quickSortFunction(arratItems, index, right);
    }
  }
  return arratItems;
};
// Initial call to quick sort function
const result = quickSortFunction(arratItems, 0, arratItems.length - 1);
console.log(result);

Run the above code line in any browser compatible with JavaScript. It will display the following outcome:

Output:

[0, 1, 2, 4, 5, 7, 8, 9]

Access the demo here.