Mastering Quicksort: Step-by-Step Breakdown

Quicksort is a divide-and-conquer algorithm that 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.

Quicksort is not a stable sorting algorithm in its standard form. Stability in sorting means that equal elements retain their relative order from the original list after sorting.

Basic Steps of Quicksort:

1. Choose a Pivot: Select an element from the array as the pivot.

2. Partitioning: Rearrange the elements in the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.

3. Recursion: Recursively apply the above steps to the sub-arrays formed by dividing at the pivot.

Implementation

function quickSort(nums: number[], s: number, e: number):void {
    if (s >= e) return;

    let pivot = nums[e];
    let left = s;

    for (let i = s; i < e; i++) {
        if (nums[i] <= pivot) {
            [nums[left], nums[i]] = [nums[i], nums[left]];
            left++;
        }
    }
    //swapping left and end index values
    [nums[left], nums[e]] = [nums[e], nums[left]];

    quickSort(nums, s, left - 1);
    quickSort(nums, left + 1, e);
}

function sortArray(nums: number[]): number[] {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

How It Works:

1. Pivot Selection: In this basic version, the pivot is selected as the last element of the array.

2. Partitioning: Elements less than or equal to the pivot are moved to the left, and those greater than the pivot are moved to the right.

3. Recursive Sorting: The algorithm then recursively sorts the sub-arrays.

Time Complexity of Quicksort

Quicksort's time complexity depends on the pivot selection and how balanced the partitioning is during each recursive call:

We have to traverse n items, and for recursion, if the array is divided in half, we get log(n) levels. Otherwise, we still have to traverse n levels.

• Best Case: when the pivot recursively divides the array into two nearly equal halves.

  $$O(nlog⁡n)$$

• Average Case: when the pivot generally creates balanced partitions.

  $$O(nlog⁡n)$$

• Worst Case: when the pivot results in highly unbalanced partitions, such as in already sorted arrays or duplicate values.

  $$O(n^2)$$

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase