Sorting

Question 1

Implement

Quick Sort using Lomuto’s method

This guarantees that the parition method will result in the pivot to be

Answer 1

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)   # Left side
        quick_sort(arr, pivot_index + 1, high) # Right side

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

Question 2

Implement

Cyclic sort
Input: arr of length n with non-repeating integers in ranges 1-n
Output: sorted arr
Time Complexity: O(n)
Space Complexity: O(1)

Answer 2

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1
        
        if nums[correct_index] != nums[i]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1
    
    return nums