TypeScript: Implement the Quick Sort Algorithm

1. Introduction

QuickSort is a highly efficient sorting algorithm that uses a divide-and-conquer strategy. This approach 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. This process is then recursively applied to the sub-arrays. In this post, we'll dive into implementing the QuickSort algorithm in TypeScript.

2. Program Overview

Our TypeScript program will consist of the main quickSort function and a helper function partition which will handle the task of dividing the array around the pivot.

3. Code Program

// Helper function to swap two elements in an array
function swap(items: number[], leftIndex: number, rightIndex: number) {
    const temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

// Helper function to find the partition position
function partition(array: number[], left: number = 0, right: number = array.length - 1): number {
    const pivot = array[Math.floor((right + left) / 2)]; // middle element
    let i = left; // left pointer
    let j = right; // right pointer
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(array, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

// Main QuickSort function
function quickSort(array: number[], left: number = 0, right: number = array.length - 1): number[] {
    if (array.length > 1) {
        const index = partition(array, left, right);
        if (left < index - 1) {
            quickSort(array, left, index - 1);
        }
        if (index < right) {
            quickSort(array, index, right);
        }
    }
    return array;
}

// Test the quickSort function
const testArray = [5, 3, 7, 6, 2, 9];
const sortedArray = quickSort(testArray);
console.log(`Original Array: ${testArray}`);
console.log(`Sorted Array: ${sortedArray}`);

Output:

Original Array: 5,3,7,6,2,9
Sorted Array: 2,3,5,6,7,9

4. Step By Step Explanation

1. The swap function is a simple utility to exchange the values of two indices in an array.

2. The partition function chooses a pivot (the middle element) and sorts the array such that all values less than the pivot come before it, and all values greater than the pivot come after it.

3. In the partition function:

- We initialize two pointers i and j at the left and right of the portion of the array we're considering.

- We then move the i pointer to the right until we find an element larger than the pivot.

- Simultaneously, we move the j pointer to the left until we find an element smaller than the pivot.

- If i is less than or equal to j, we swap the elements at i and j and then move both pointers.

4. The main quickSort function recursively sorts smaller portions of the array, utilizing the partitioning process.

5. We call the quickSort function recursively for the left and right sub-arrays.

6. Finally, we test our quickSort function using an example array and display the results using console.log.

This TypeScript implementation of the QuickSort algorithm is efficient and showcases the power of recursive problem-solving.