How To Write Quicksort: In Typescript

Introduction:

When we talk about sorting algorithms, Quick Sort is one of the most widely used ones. It is a fast, efficient, and in-place algorithm. Typescript on the other hand, is a superset of Javascript which adds static typing, class-based object-oriented programming, and improved syntax to the language. It has gained popularity among developers due to its advantages like improved performance, code readability, and enhanced tooling support. In this article, we will learn how to write Quick Sort in Typescript. We will begin by understanding the basic implementation of Quick Sort and then move on to the time complexity analysis. After that, we will look at some optimization techniques for Quick Sort and finally, we will see an example of Quick Sort application in Typescript.

Basic Quick Sort Implementation:

Before we start with the Quick Sort implementation in Typescript, let’s understand the algorithm first. Quick Sort is a divide and conquer 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 recursively sorted.

Here are the steps to implement Quick Sort in Typescript:

Step 1: Define the Quick Sort function

We will start by defining the Quick Sort function. This function will take the array as input and it will return the sorted array as output.

function quickSort(array: Array<number>) : Array<number> {
    return array;
}

Step 2: Define the Base Case

In order to implement the Quick Sort algorithm recursively, we need to define the base case. The base case is an array with only one element. As an array with only one element is already sorted, we can just return it.

function quickSort(array: Array<number>) : Array<number> {
    if (array.length <= 1) {
        return array;
    }
    return array;
}

Step 3: Choose a Pivot Element

Now, we need to choose a pivot element from the array. There are many ways to choose a pivot element, but for simplicity, we will always choose the last element of the array as the pivot.

function quickSort(array: Array<number>) : Array<number> {
    if (array.length <= 1) {
        return array;
    }
    const pivot = array[array.length - 1];
    return array;
}

Step 4: Partition the Array

We will partition the array into two sub-arrays, one with elements smaller than the pivot and one with elements greater than the pivot. We will also create a third sub-array for the elements equal to the pivot.

function quickSort(array: Array<number>) : Array<number> {
    if (array.length <= 1) {
        return array;
    }
    const pivot = array[array.length - 1];
    const leftArray = [];
    const rightArray = [];
    const equalArray = [];
    for (let element of array) {
        if (element < pivot) {
            leftArray.push(element);
        } else if (element > pivot) {
            rightArray.push(element);
        } else {
            equalArray.push(element);
        }
    }
    return array;
}

Step 5: Recursively Sort the Sub-Arrays

Now, we will recursively sort the left and right sub-arrays. We will also concatenate the sub-arrays in this way: left sub-array, equal sub-array, and right sub-array.

function quickSort(array: Array<number>) : Array<number> {
    if (array.length <= 1) {
        return array;
    }
    const pivot = array[array.length - 1];
    const leftArray = [];
    const rightArray = [];
    const equalArray = [];
    for (let element of array) {
        if (element < pivot) {
            leftArray.push(element);
        } else if (element > pivot) {
            rightArray.push(element);
        } else {
            equalArray.push(element);
        }
    }
    return [...quickSort(leftArray), ...equalArray, ...quickSort(rightArray)];
}

Time Complexity Analysis of Quick Sort:

In order to analyze the time complexity of Quick Sort, we need to calculate the average case and worst case time complexity.

Average Case Time Complexity:

The average case time complexity of Quick Sort is O(nlogn). This means that for an array of n elements, the time required to sort it is proportional to nlogn.

We can calculate the average case time complexity using the following equation:

T (n) = 2 * T (n/2) + O(n)

Where,
T(n) = Time complexity of Quick Sort for an array of n elements
O(n) = Time required for partitioning the array
2 * T(n/2) = Time required for sorting the left and right sub-arrays

Worst Case Time Complexity:

The worst case time complexity of Quick Sort is O(n^2). This happens when the pivot element is either the smallest or the largest element in the array. In this case, the partitioning creates two sub-arrays of size 0 and n-1, respectively. This leads to a recurrence relation similar to that of insertion sort (O(n^2)).

We can calculate the worst case time complexity using the following equation:

T (n) = T (n-1) + O(n)
= O(n^2)

Optimization Techniques for Quick Sort:

There are many optimization techniques for Quick Sort. Some of them are:

Choosing a Pivot:
The choice of pivot element can greatly affect the performance of the Quick Sort algorithm. Some techniques to choose the pivot are:

1. First Element: Choose the first element as the pivot.
2. Random Element: Choose a random element as the pivot.
3. Median of Three: Choose the median of the first, middle, and last element as the pivot.

Three-way Partitioning:

In the basic implementation of Quick Sort, if we have multiple elements that are equal to the pivot, they will all be placed in the equal sub-array. If the number of equal elements is very large, this can cause performance issues. Three-way partitioning is a technique to partition the array into three sub-arrays: one with elements smaller than the pivot, one with elements equal to the pivot, and one with elements greater than the pivot.

Hybrid Sorting:

In some cases, using hybrid sorting can improve the performance of Quick Sort. Hybrid sorting is a technique of using another sorting algorithm like Heap Sort or Insertion Sort for smaller sub-arrays. This happens because, for very small sub-arrays, the overhead of recursion in Quick Sort becomes more than the efficiency of sorting algorithm.

Example of Quick Sort Application in Typescript:

Here is an example of Quick Sort application in Typescript:

function quickSort(array: Array<number>) : Array<number> {
    if (array.length <= 1) {
        return array;
    }
    const pivot = array[array.length - 1];
    const leftArray = [];
    const rightArray = [];
    const equalArray = [];
    for (let element of array) {
        if (element < pivot) {
            leftArray.push(element);
        } else if (element > pivot) {
            rightArray.push(element);
        } else {
            equalArray.push(element);
        }
    }
    return [...quickSort(leftArray), ...equalArray, ...quickSort(rightArray)];
}

const array = [5, 1, 3, 7, 8, 2, 6];
console.log(quickSort(array)); // Output: [1, 2, 3, 5, 6, 7, 8]

In this example, we take an array

of random integers and apply the Quick Sort function on it. The output will be the sorted array. The output should be [1, 2, 3, 5, 6, 7, 8].

Conclusion:

In this article, we learned how to implement Quick Sort in Typescript. We started by understanding the basic implementation of Quick Sort and then moved on to the time complexity analysis. We saw that the average case time complexity of Quick Sort is O(nlogn) and the worst case time complexity is O(n^2). Then we discussed some optimization techniques for Quick Sort like choosing a pivot, three-way partitioning, and hybrid sorting. Finally, we saw an example of Quick Sort application in Typescript. Quick Sort is a very important algorithm and is widely used in real-world applications. By learning how to implement it in Typescript, we have gained a valuable skill that can be useful in many projects.