Quick Sort with Pivot Selection

Quick Sort with Pivot Selection

The Quick Sort Algorithm is an efficient, divide-and-conquer sorting 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 recursively sorted. Pivot selection is critical to performance: common strategies include choosing the first element, last element, middle element, or a random element. Here, we use the last element as the pivot for simplicity, though this can lead to O(n²) time complexity in the worst case (e.g., already sorted arrays). For better performance in practice, alternatives like median-of-three or random pivot selection can be used.

Example

• Input: nums = [64, 34, 25, 12, 22, 11, 90]
• Output: [11, 12, 22, 25, 34, 64, 90]
• Explanation: The array is sorted in ascending order.

def quickSort(nums, low, high):
    def partition(low, high):
        pivot = nums[high]
        i = low - 1  # Index of smaller element
        for j in range(low, high):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[high] = nums[high], nums[i + 1]
        return i + 1

    if low < high:
        # Find pivot position
        pi = partition(low, high)
        # Recursively sort elements before and after partition
        quickSort(nums, low, pi - 1)
        quickSort(nums, pi + 1, high)
    return nums

# Example usage
nums = [64, 34, 25, 12, 22, 11, 90]
quickSort(nums, 0, len(nums) - 1)
print(nums)  # Output: [11, 12, 22, 25, 34, 64, 90]

[11, 12, 22, 25, 34, 64, 90]

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE