The QuickSort algorithm is a divide-and-conquer sorting technique that uses the partition function to reorder an array such that all elements less than or equal to the pivot are on its left. The quicksort function recursively sorts the left and right subarrays generated by partitioning the input array until the base case is reached, where the subarray contains only one element or is empty.

Cell 11

def quicksort(nums, start=0, end=None):
    """Quicksort using last element as pivot."""
    def partition(nums, start, end):
        pindex = start
        pivot = end
        for i in range(start, end):
            if nums[i] <= nums[pivot]:
                nums[i], nums[pindex] = nums[pindex], nums[i]
                pindex += 1
        nums[pindex], nums[pivot] = nums[pivot], nums[pindex]
        return pindex
    if not end:
        end = len(nums)-1
    if start >= end:
        return None
    pivot = partition(nums, start, end)
    quicksort(nums, start, pivot-1)
    quicksort(nums, pivot+1, end)
    
a = [2, 9, 2, 3, 5, 8, 1]
quicksort(a)
assert a == [1, 2, 2, 3, 5, 8, 9]
print('All passed!')

def quicksort(nums: list, start: int = 0, end: int = None) -> None:
    """
    Sorts the input list in-place using the Quicksort algorithm.

    Args:
        nums (list): The list to be sorted.
        start (int, optional): The starting index of the sublist to be sorted. Defaults to 0.
        end (int, optional): The ending index of the sublist to be sorted. Defaults to the last index of the list.

    Returns:
        None
    """
    if end is None:
        end = len(nums) - 1
    
    if start >= end:
        return

    partition_index = partition(nums, start, end)
    quicksort(nums, start, partition_index - 1)
    quicksort(nums, partition_index + 1, end)


def partition(nums: list, start: int, end: int) -> int:
    """
    Partitions the sublist around the pivot element.

    Args:
        nums (list): The list to be partitioned.
        start (int): The starting index of the sublist.
        end (int): The ending index of the sublist.

    Returns:
        int: The index of the pivot element after partitioning.
    """
    pivot = nums[end]
    i = start - 1
    for j in range(start, end):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[end] = nums[end], nums[i + 1]
    return i + 1


# Test the implementation
a = [2, 9, 2, 3, 5, 8, 1]
quicksort(a)
assert a == [1, 2, 2, 3, 5, 8, 9]
print('All passed!')

QuickSort Algorithm Implementation

Overview

The provided code implements the QuickSort algorithm, a popular sorting technique that uses a divide-and-conquer approach to sort an array of elements.

Functions

quicksort(nums, start=0, end=None)

• Sorts the input array nums using the QuickSort algorithm.
• start and end specify the range of elements to sort. If not provided, the function sorts the entire array.
• Returns None if the input array is empty or contains only one element.

partition(nums, start, end)

• Reorders the input array nums to have all elements less than or equal to the pivot element at the end of the range.
• Returns the index of the pivot element after reordering.

Algorithm

1. The partition function is used to choose a pivot element and reorder the input array such that all elements less than or equal to the pivot are on its left.
2. The quicksort function recursively sorts the left and right subarrays generated by partitioning the input array.
3. The base case for recursion is when the subarray contains only one element or is empty, in which case the function returns None.

Example Usage

a = [2, 9, 2, 3, 5, 8, 1]
quicksort(a)
assert a == [1, 2, 2, 3, 5, 8, 9]

This example sorts the input array a using the QuickSort algorithm and verifies that the sorted array matches the expected result.