Quicksort Algorithm

The provided code implements the quicksort algorithm, a highly efficient sorting algorithm known for its average-case performance of O(n log n) and ability to operate in place. Here's a conceptual overview of how the code works:

Conceptual Overview of Quicksort Algorithm

Partitioning the Array

Recursively Sorting Subarrays

After partitioning, the algorithm recursively sorts the left and right subarrays using the same process. This recursion continues until the subarrays have one or fewer elements, indicating that they are already sorted.

Base Case

The recursion stops when the start index becomes greater than or equal to the end index, indicating that the subarray has one or fewer elements.

The subarray is sorted at this point, and the algorithm moves on to the next step.

Choosing the Pivot

The pivot element is initially chosen as the first element of the subarray.

The algorithm then partitions the subarray around this pivot element.

Swapping Elements

During the partitioning step, elements are swapped within the subarray to ensure that all elements smaller than the pivot are on its left and all elements greater than the pivot are on its right.

This swapping process continues until the left and right pointers meet.

Recursive Sorting

After partitioning, the algorithm determines which subarray is smaller (left or right) to optimize performance.

It then recursively sorts the smaller subarray first to minimize the recursion depth and reduce the number of recursive calls.

Returning the Sorted Array

Once all recursive calls have been completed and the array is fully sorted, the algorithm returns the sorted array to the caller.

# O(nlog(n)) time | O(log(n)) space
def quick_sort(array):
    """
    Sorts the given array in ascending order using the quicksort algorithm.

    Parameters:
        array (list): The input list of integers to be sorted.

    Returns:
        list: The sorted list.
    """
    quick_sort_helper(array, 0, len(array) - 1)
    return array

def quick_sort_helper(array, startIdx, endIdx):
    """
    Helper function for the quicksort algorithm.

    Parameters:
        array (list): The input list of integers.
        startIdx (int): The starting index of the subarray.
        endIdx (int): The ending index of the subarray.
    """
    # Base case: if the subarray has one or fewer elements, it is already sorted
    if startIdx >= endIdx:
        return
    
    # Selecting the pivot and initializing left and right pointers
    pivotIdx = startIdx
    leftIdx = startIdx + 1
    rightIdx = endIdx
    
    # Partitioning the subarray
    while rightIdx >= leftIdx:
        # Move the left index until encountering an element greater than the pivot
        # and simultaneously move the right index until encountering an element smaller than the pivot.
        # Once both indices have found elements violating the partition rule,
        # swap them to correct the partition.
        if array[leftIdx] > array[pivotIdx] and array[rightIdx] < array[pivotIdx]:
            swap(leftIdx, rightIdx, array)
        if array[leftIdx] <= array[pivotIdx]:
            leftIdx += 1
        if array[rightIdx] >= array[pivotIdx]:
            rightIdx -= 1
    
    # Swap the pivot with the right index to place it in its final sorted position
    swap(pivotIdx, rightIdx, array)
    
    # Recursively sort the left and right subarrays
    leftSubarrayIsSmaller = rightIdx - 1 - startIdx < endIdx - (rightIdx + 1)
    if leftSubarrayIsSmaller:
        quick_sort_helper(array, startIdx, rightIdx - 1)
        quick_sort_helper(array, rightIdx + 1, endIdx)
    else:
        quick_sort_helper(array, rightIdx + 1, endIdx)
        quick_sort_helper(array, startIdx, rightIdx - 1)

def swap(i, j, array):
    """
    Swaps the elements at the specified indices in the given array.

    Parameters:
        i (int): The index of the first element to swap.
        j (int): The index of the second element to swap.
        array (list): The input list of integers.
    """
    array[i], array[j] = array[j], array[i]



import unittest

class TestQuickSort(unittest.TestCase):
    def test_quick_sort(self):
        # Test case with a randomly shuffled array
        array1 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
        self.assertEqual(quick_sort(array1), sorted(array1))

        # Test case with an already sorted array
        array2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        self.assertEqual(quick_sort(array2), sorted(array2))

        # Test case with a reverse-sorted array
        array3 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
        self.assertEqual(quick_sort(array3), sorted(array3))

        # Test case with an empty array
        array4 = []
        self.assertEqual(quick_sort(array4), [])

        # Test case with a single-element array
        array5 = [42]
        self.assertEqual(quick_sort(array5), [42])

        # Test case with an array containing duplicate elements
        array6 = [5, 2, 1, 4, 2, 3, 5, 1]
        self.assertEqual(quick_sort(array6), sorted(array6))

        self.assertEqual(quick_sort([8,5,9,5,6,3]), sorted([8,5,9,5,6,3]))

if __name__ == "__main__":
    unittest.main()

Time & Space Complexity

Here's the analysis of the time and space complexity of the quicksort algorithm:

Time Complexity

•     Best Case: O(n log n)
•     Average Case: O(n log n)
•     Worst Case: O(n^2)

In the best and average cases, quicksort demonstrates excellent performance with a time complexity of O(n log n). This complexity arises from the logarithmic partitioning of the array, where each partitioning step divides the array approximately in half.

As a result, the total number of partitioning steps required to sort the entire array is proportional to n log n.

However, quicksort's time complexity can degrade to O(n^2) in the worst case. This occurs when the pivot selection consistently creates unbalanced partitions, such as when the pivot is consistently chosen as the smallest or largest element in the array.

Quicksort performs similarly to insertion sort in such scenarios, resulting in a quadratic time complexity.

Space Complexity

•     O(log n) on average
•     O(n) worst case (due to recursion stack)

The space complexity of quicksort primarily depends on the depth of the recursion stack. On average, the recursion depth is O(log n) because the algorithm typically divides the array into roughly equal halves at each step.

As a result, the maximum number of recursive calls required is logarithmic with respect to the input size.

However, in the worst case (when the partitioning is highly unbalanced), the recursion depth could be as high as O(n), leading to a worst-case space complexity of O(n) due to the recursion stack.

This situation occurs when the pivot selection consistently creates unbalanced partitions, leading to inefficient memory use.

Key Points

• Quick sort is a divide-and-conquer algorithm that operates in place, making it memory efficient.
• It achieves the average-case time complexity of O(n log n) due to its logarithmic partitioning.
• However, its worst-case time complexity can degrade to O(n^2) if the pivot selection consistently creates unbalanced partitions.
• The algorithm is widely used in practice due to its average-case performance and simplicity of implementation.