Blog

Title: Understanding Quick Sort in TypeScript: A Step-by-Step Guide

---

When it comes to sorting algorithms, Quick Sort is one of the fastest and most efficient options available. In this blog post, we will explore the Quick Sort algorithm, how it works, and implement it in TypeScript.

Quick Sort Overview

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

TypeScript Implementation

Let’s dive into the TypeScript implementation of Quick Sort. We’ll break it down into several steps for clarity.

Step 1: Choose a Pivot

The first step is to choose a pivot element from the array. A commonly used strategy is to select the last element in the array as the pivot. We will start our implementation by creating a function to choose the pivot.

function choosePivot(arr: number[], low: number, high: number): number {
  // We'll choose the last element as the pivot
  return arr[high];
}

Step 2: Partition the Array

Next, we need to partition the array into two sub-arrays – elements less than the pivot and elements greater than the pivot. We’ll create a partition function for this purpose.

function partition(arr: number[], low: number, high: number): number {
  const pivot = choosePivot(arr, low, high);
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      // Swap arr[i] and arr[j]
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  // Swap arr[i + 1] and arr[high] to place pivot in the correct position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

  return i + 1;
}

Step 3: Recursive Sorting

Now that we have a function to partition the array, we can implement the main Quick Sort function that recursively sorts the sub-arrays.

function quickSort(arr: number[], low: number, high: number): void {
  if (low < high) {
    const pi = partition(arr, low, high);

    // Recursively sort elements before and after partition
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

Step 4: Putting It All Together

Finally, let’s create a wrapper function that simplifies the sorting process.

function sort(arr: number[]): number[] {
  const copyArr = [...arr]; // Create a copy to avoid modifying the original array
  quickSort(copyArr, 0, copyArr.length - 1);
  return copyArr;
}

Example Usage

You can use the sort function to sort an array of numbers. Here’s an example:

const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = sort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 64]

Conclusion

Quick Sort is a highly efficient sorting algorithm that works well for large datasets. Understanding its inner workings and implementing it in TypeScript can be a valuable addition to your programming toolkit.