Adventures in Machine Learning

Mastering QuickSort: An Efficient Algorithm for Large Datasets

Understanding the QuickSort Algorithm

When it comes to sorting algorithms, QuickSort is often considered one of the most efficient. It’s fast, easy to understand, and can handle large sets of data with ease.

In this article, we’ll take a closer look at how QuickSort works and what makes it so effective.

Selecting a Pivot element

The first step in QuickSort is to select a pivot element. The pivot element is the element around which other elements will be rearranged.

Choosing the pivot element can be done using various algorithms, but the most common approach is to pick the first element in the array.

Rearranging elements around Pivot

Once we have our pivot element, we can rearrange the remaining elements around it. There are different ways to do this, but a common approach is to move all elements smaller than the pivot to the left of it and all elements larger than the pivot to the right of it.

This is known as the partitioning step. How to move low and high?

To move the low and high elements around the pivot, we use two pointers – one for the low values and one for the high values. We start with the low pointer at the beginning of the array and the high pointer at the end.

We then move the low pointer to the right until we find an element that is greater than the pivot, and we move the high pointer to the left until we find an element that is less than the pivot. Once we have found the elements to swap, we swap them and continue with the process of moving the low and high pointers until they meet.

At this point, we know that all elements to the left of the pivot are less than or equal to it, and all elements to the right are greater than or equal to it.

Implemented Code Until Now

Let’s take a look at the code we’ve implemented so far:

function quickSort(array, low, high) {
  if (low < high) {
    // select pivot element
    let pivotIndex = partition(array, low, high);
    // recursively sort two halves of the array
    quickSort(array, low, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, high);
  }
}
function partition(array, low, high) {
  // select pivot element
  let pivotValue = array[low];
  let leftPointer = low + 1;
  let rightPointer = high;
  while (leftPointer <= rightPointer) {
    // find element on left side to swap with element on right side
    while (array[leftPointer] < pivotValue) {
      leftPointer++;
    }
    // find element on right side to swap with element on left side
    while (array[rightPointer] > pivotValue) {
      rightPointer--;
    }
    if (leftPointer <= rightPointer) {
      // swap elements
      let temp = array[leftPointer];
      array[leftPointer] = array[rightPointer];
      array[rightPointer] = temp;
      leftPointer++;
      rightPointer--;
    }
  }
  // move pivot element to its correct position
  let temp = array[low];
  array[low] = array[rightPointer];
  array[rightPointer] = temp;
  return rightPointer;
}

As you can see, we’ve implemented the partitioning step, where we select the pivot element and rearrange the remaining elements around it. We’re also making recursive calls on the two halves of the array, which will allow us to sort the entire array.

Make recursive calls on two halves of the array

Finally, we need to make recursive calls on the two halves of the array. We’ll pass in the updated low and high indexes to ensure we’re only sorting the elements between those indexes.

This process will continue until we have sorted the entire array. Here’s the final version of our code:

function quickSort(array, low, high) {
  if (low < high) {
    // select pivot element
    let pivotIndex = partition(array, low, high);
    // recursively sort two halves of the array
    quickSort(array, low, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, high);
  }
}
function partition(array, low, high) {
  // select pivot element
  let pivotValue = array[low];
  let leftPointer = low + 1;
  let rightPointer = high;
  while (leftPointer <= rightPointer) {
    // find element on left side to swap with element on right side
    while (array[leftPointer] < pivotValue) {
      leftPointer++;
    }
    // find element on right side to swap with element on left side
    while (array[rightPointer] > pivotValue) {
      rightPointer--;
    }
    if (leftPointer <= rightPointer) {
      // swap elements
      let temp = array[leftPointer];
      array[leftPointer] = array[rightPointer];
      array[rightPointer] = temp;
      leftPointer++;
      rightPointer--;
    }
  }
  // move pivot element to its correct position
  let temp = array[low];
  array[low] = array[rightPointer];
  array[rightPointer] = temp;
  return rightPointer;
}
let array = [5, 3, 6, 4, 2, 8, 9, 1, 7];
quickSort(array, 0, array.length - 1);
console.log(array); // output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Example of the QuickSort Array

To illustrate the effectiveness of QuickSort, consider the following example:

Let’s say we have an array of integers – [5, 3, 6, 4, 2, 8, 9, 1, 7]. Using QuickSort, we can sort this array in just a few steps.

First, we’ll select the pivot element. Since we’re using the first element in the array as the pivot, our pivot value is 5.

Next, we’ll rearrange the remaining elements around the pivot. We’ll move all elements smaller than 5 to the left of it and all elements greater than 5 to the right of it.

The resulting array is [1, 3, 2, 4, 5, 8, 9, 6, 7]. We’ll repeat this process on the two halves of the array.

First, we’ll sort the left half, which is [1, 3, 2, 4]. We’ll select 1 as the pivot element and rearrange the remaining elements around it.

The resulting array is [1, 3, 2, 4], which is already sorted. Next, we’ll sort the right half, which is [8, 9, 6, 7].

We’ll select 8 as the pivot element and rearrange the remaining elements around it. The resulting array is [6, 7, 8, 9], which is also sorted.

Finally, we’ll merge the two sorted halves to get the final, sorted array – [1, 2, 3, 4, 5, 6, 7, 8, 9]. As you can see, with just a few steps, we were able to sort a relatively large array with ease.

Conclusion

QuickSort is an efficient sorting algorithm that is easy to understand and implement. By selecting a pivot element, rearranging the remaining elements around it, and recursively sorting the two halves of the array, we’re able to sort even large datasets with relative ease.

While there are other sorting algorithms available, QuickSort is often the go-to approach for many developers due to its speed and simplicity.

Complete implementation

In the previous sections of this article, we discussed the Quicksort algorithm, including selecting a pivot element, rearranging elements around the pivot, and recursively sorting two halves of the array. Now, let’s take a look at the complete implementation of the Quicksort algorithm.

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  
  const pivotIndex = Math.floor(array.length / 2);
  const pivotValue = array[pivotIndex];
  
  const left = [];
  const right = [];
  
  for (let i = 0; i < array.length; i++) {
    if (i === pivotIndex) {
      continue;
    }
    
    if (array[i] < pivotValue) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  
  return [
    ...quickSort(left),
    pivotValue,
    ...quickSort(right)
  ];
}

The above code implements a basic Quicksort algorithm that takes an array of numbers as input and returns a new array with the same numbers but sorted using the algorithm. Let’s walk through the code step by step:

  1. The `quickSort` function takes an array of numbers as input.

  2. We check if the length of the array is less than or equal to 1. If so, we simply return the array since it is already sorted, and there is no need to sort it again.

  3. We select the pivot element by finding the middle index of the array using `Math.floor(array.length / 2)`.

  4. We then store the value of the pivot element in `pivotValue`.

  5. We create two new arrays, `left` and `right`, to store elements smaller than the pivot and elements greater than or equal to the pivot, respectively.

  6. We iterate over each element in the input array and ignore the pivot element. If an element is smaller than the pivot, we push it into the `left` array, otherwise, we push it into the `right` array.

  7. We recursively call the `quickSort` function on the `left` and `right` arrays, and concatenate the sorted results with the pivot value in between them, using the spread operator (`…`).

  8. The final sorted array is returned.

This implementation is slightly different from the one we discussed earlier. Instead of relying on in-place swapping of elements, this implementation creates new arrays for elements smaller and greater than the pivot value, and recursively sorts them.

While this approach takes up more memory, it is often simpler to understand and implement. Let’s test our implementation with a sample array:

const unsortedArray = [10, 5, 2, 3, 7, 6, 8, 1, 4, 9];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

As expected, the resulting array is sorted in ascending order.

Quicksort optimization

While the above implementation works fine and is easy to understand, it is not the most efficient version of the algorithm. In particular, it can run into performance problems when sorting large datasets.

Two common optimizations to the Quicksort algorithm are:

  1. Using a random pivot – Instead of using the first element of the array as the pivot, we can randomly select an element.

  2. Using tail recursion – In the recursive calls of the Quicksort algorithm, we can eliminate the need for function call stack space by using tail recursion. Tail recursion is an optimization technique where the function call is the last operation performed, and the result is returned directly without performing any further operations.

This can greatly reduce the amount of memory used by the algorithm and improve its performance. Here is an optimized version of the Quicksort algorithm that incorporates both of these optimizations:

function quickSort(array, low = 0, high = array.length - 1) {
  while (low < high) {
    const pivotIndex = partition(array, low, high);
    if (pivotIndex - low < high - pivotIndex) {
      quickSort(array, low, pivotIndex - 1);
      low = pivotIndex + 1;
    } else {
      quickSort(array, pivotIndex + 1, high);
      high = pivotIndex - 1;
    }
  }
  return array;
}
function partition(array, low, high) {
  const pivotIndex = Math.floor(Math.random() * (high - low + 1) + low);
  const pivotValue = array[pivotIndex];
  swap(array, pivotIndex, high);
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (array[j] < pivotValue) {
      i++;
      swap(array, i, j);
    }
  }
  swap(array, i + 1, high);
  return i + 1;
}
function swap(array, i, j) {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

In this implementation, we use a random pivot value and perform tail recursion by updating the `low` and `high` indexes based on which half of the array is smaller.

We also use the `swap` function to swap elements in the array. Let’s test our optimized implementation with a larger array:

const unsortedArray = [10, 5, 2, 3, 7, 6, 8, 1, 4, 9, 20, 13, 18, 15, 16, 11, 19, 17, 12, 14];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

As expected, the resulting array is sorted in ascending order, and the optimization has significantly improved the performance of the algorithm.

Conclusion

Quicksort is a simple yet powerful sorting algorithm that can handle large datasets with ease. While it has its drawbacks, such as a worst-case scenario where the pivot value is the largest or smallest element in the array, there are various optimizations that can be applied to improve its performance.

The optimized implementation of Quicksort using a random pivot and tail recursion can greatly reduce the algorithm’s memory footprint and make it more efficient. In this article, we discussed the Quicksort algorithm, a fast and efficient way of sorting large datasets.

We covered the key steps involved in the algorithm, such as selecting a pivot element, rearranging elements around the pivot, and recursively sorting two halves of the array. We also provided a complete implementation of the algorithm and discussed two common optimizations that can improve its performance: using a random pivot and using tail recursion.

Quicksort is an important topic for any developer looking to optimize their algorithms, and the takeaways from this article can help improve their understanding of the algorithm and its implementation.

Popular Posts