Implementation of Quick Sort Algorithm in JavaScript

Quick Sort is a highly efficient and popular algorithm for sorting lists or arrays. It works by breaking down the sorting problem into smaller, more manageable pieces and solving them. In this article, we’ll guide you through implementing the Quick Sort algorithm using JavaScript, step by step. We’ll start with a basic version and explore variations like sorting in reverse order and sorting lists of custom objects.

Prerequisites:

Core Idea Recap

Before diving into the JavaScript code, let’s quickly recall the main steps of Quick Sort:

  1. Choose a Pivot: Pick an element from the array to act as a reference point (the pivot).
  2. Partition: Rearrange the array so that all elements smaller than the pivot are placed to its left, and all elements larger are placed to its right. After this step, the pivot is in its final sorted position.
  3. Recurse: Apply the Quick Sort algorithm recursively to the sub-arrays on the left and right sides of the pivot.
  4. Base Case: The recursion stops when a sub-array contains zero or one element, as these are already considered sorted.

Basic Quick Sort Implementation (Recursive)

Let’s implement Quick Sort in JavaScript using recursion. We’ll create two main functions: quickSort for the overall recursive logic and partition for rearranging the array around the pivot. For simplicity, we’ll use the last element as the pivot in our partition function.

The swap Helper Function

First, let’s create a small helper function to swap two elements in an array. This will make our partition function cleaner.

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

The partition Function

This function takes the array (or a sub-array defined by low and high indices) as input. It rearranges the elements around the pivot (the last element) and returns the pivot’s final index.

function partition(arr, low, high) {
  // Choose the last element as the pivot
  let pivot = arr[high];
  
  // i tracks the index for the "boundary" of elements smaller than the pivot
  // It starts one position before the beginning of the sub-array
  let i = low - 1; 

  // Iterate through the sub-array from 'low' up to (but not including) 'high'
  for (let j = low; j < high; j++) {
    // If the current element (arr[j]) is smaller than or equal to the pivot
    if (arr[j] <= pivot) {
      // Increment the boundary index 'i'
      i++;
      // Swap the element at the boundary (arr[i]) with the current element (arr[j])
      // This moves the smaller element arr[j] to the left side of the boundary
      swap(arr, i, j);
    }
  }

  // After the loop, the correct position for the pivot is right after the boundary 'i'
  // Swap the pivot (arr[high]) with the element at arr[i + 1]
  swap(arr, i + 1, high);
  
  // Return the index where the pivot was placed
  return i + 1; 
}

Explanation:

  • pivot = arr[high]: We select the last element as our reference pivot.
  • i = low - 1: i acts as a pointer to the end of the section containing elements smaller than the pivot. It starts before the current sub-array.
  • The for loop iterates from low to high - 1.
  • if (arr[j] <= pivot): If we find an element smaller than or equal to the pivot, we increment i (extending the “smaller” section) and swap arr[i] with arr[j]. This effectively moves the smaller element arr[j] into the “smaller” section.
  • swap(arr, i + 1, high): After checking all elements, the pivot (originally arr[high]) is placed just after the last smaller element found, which is position i + 1.
  • return i + 1: The function returns the index where the pivot now resides.

The quickSort Function

This function implements the recursive logic. It calls partition to place the pivot correctly and then recursively calls itself on the two resulting sub-arrays (left and right of the pivot).

function quickSort(arr, low, high) {
  // Base case: If low is less than high, there's more than one element to sort
  if (low < high) {
    // Partition the array, pi is the index of the pivot in its correct place
    let pi = partition(arr, low, high);

    // Recursively sort the sub-array before the pivot (elements low to pi-1)
    quickSort(arr, low, pi - 1);

    // Recursively sort the sub-array after the pivot (elements pi+1 to high)
    quickSort(arr, pi + 1, high);
  }
}

Explanation:

  • if (low < high): This check serves as the base case. If low is greater than or equal to high, the sub-array has 0 or 1 element, meaning it’s already sorted, and the recursion stops for this branch.
  • pi = partition(arr, low, high): Calls the partition function to rearrange the current sub-array and find the pivot’s final position pi.
  • quickSort(arr, low, pi - 1): Makes a recursive call to sort the elements to the left of the pivot.
  • quickSort(arr, pi + 1, high): Makes a recursive call to sort the elements to the right of the pivot.

Putting It Together

Let’s see how to use these functions to sort a JavaScript array:

// Helper function to swap elements
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// Partition function (chooses last element as pivot)
function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1; 

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return i + 1; 
}

// Main Quick Sort function
function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

// --- Example Usage ---
let myArray = [10, 7, 8, 9, 1, 5];
let n = myArray.length;

console.log("Original array:", myArray);

// Initial call to quickSort
// Pass the array, the starting index (0), and the ending index (n-1)
quickSort(myArray, 0, n - 1);

console.log("Sorted array:", myArray);
// Output:
// Original array: [ 10, 7, 8, 9, 1, 5 ]
// Sorted array: [ 1, 5, 7, 8, 9, 10 ]

Sorting in Descending Order

Want to sort from largest to smallest? It’s a very small change! Just flip the comparison operator in the partition function from <= to >=.

// Partition function modified for descending order
function partitionDescending(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1; 
  for (let j = low; j < high; j++) {
    // Change comparison to >= for descending sort
    if (arr[j] >= pivot) { 
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return i + 1; 
}

// Quick Sort function modified to use the descending partition
function quickSortDescending(arr, low, high) {
  if (low < high) {
    // Use the descending partition function
    let pi = partitionDescending(arr, low, high); 
    quickSortDescending(arr, low, pi - 1);
    quickSortDescending(arr, pi + 1, high);
  }
}

// --- Example Usage ---
let arrayDesc = [10, 7, 8, 9, 1, 5];
console.log("\nOriginal array for descending sort:", arrayDesc);
quickSortDescending(arrayDesc, 0, arrayDesc.length - 1);
console.log("Sorted array (descending):", arrayDesc);
// Output:
// Original array for descending sort: [ 10, 7, 8, 9, 1, 5 ]
// Sorted array (descending): [ 10, 9, 8, 7, 5, 1 ]

Sorting Custom Objects

Quick Sort is versatile! You can use it to sort arrays of objects based on specific properties (like age or name). To do this, we’ll modify our functions to accept an optional compareFunc. This function will tell Quick Sort how to compare two objects.

// Helper function (remains the same)
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// Partition function accepting a compare function
function partitionCustom(arr, low, high, compareFunc) {
  let pivot = arr[high]; // The object acting as pivot
  let i = low - 1; 

  for (let j = low; j < high; j++) {
    // Use the compareFunc to decide order:
    // compareFunc(a, b) < 0 means 'a' should come before 'b'
    // compareFunc(a, b) <= 0 means 'a' can come before or is equal to 'b'
    if (compareFunc(arr[j], pivot) <= 0) { 
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return i + 1; 
}

// Quick Sort function accepting a compare function
function quickSortCustom(arr, low, high, compareFunc) {
  // Default comparison for numbers if no compareFunc is provided
  if (!compareFunc) {
      compareFunc = (a, b) => a - b; 
  }

  if (low < high) {
    let pi = partitionCustom(arr, low, high, compareFunc);
    quickSortCustom(arr, low, pi - 1, compareFunc);
    quickSortCustom(arr, pi + 1, high, compareFunc);
  }
}

// --- Example Usage with Objects ---
let students = [
  { name: "Alice", age: 22 },
  { name: "Bob", age: 20 },
  { name: "Charlie", age: 25 },
  { name: "David", age: 22 } 
];

console.log("\nOriginal student list:", students);

// Define a comparison function for sorting by age (ascending)
function compareStudentsByAge(studentA, studentB) {
  return studentA.age - studentB.age; // Negative if A < B, 0 if A == B, Positive if A > B
}

// Sort the students by age
quickSortCustom(students, 0, students.length - 1, compareStudentsByAge);
console.log("Sorted student list by age:", students);
// Note: Quick Sort isn't stable, order of Alice & David (same age) might vary.

// Define a comparison function for sorting by name (ascending)
function compareStudentsByName(studentA, studentB) {
    if (studentA.name < studentB.name) return -1;
    if (studentA.name > studentB.name) return 1;
    return 0;
}

// Sort the students by name
quickSortCustom(students, 0, students.length - 1, compareStudentsByName);
console.log("Sorted student list by name:", students);

Explanation:

  1. The partitionCustom and quickSortCustom functions now accept an additional compareFunc argument.
  2. The compareFunc is expected to work like the comparison function used by JavaScript’s built-in Array.prototype.sort(). It should return:
    • A negative number if the first element should come before the second.
    • Zero if the elements are considered equal for sorting purposes.
    • A positive number if the first element should come after the second.
  3. Inside partitionCustom, if (compareFunc(arr[j], pivot) <= 0) uses this function to determine if arr[j] should be placed in the “smaller or equal” section relative to the pivot.
  4. We provide specific comparison functions (compareStudentsByAge, compareStudentsByName) when calling quickSortCustom to sort the students array based on different criteria.

What’s Next?

Now that you’ve seen how to implement Quick Sort in JavaScript, you can delve deeper into its characteristics and applications: