Sorting: Quick Sort

Sorting: Quick Sort

 

 

https://youtu.be/QaFmEzMtYu8

 

https://youtu.be/OYnYbSC-Y_w

 

# Implementation of QuickSort
def quickSort(arr: list[int], s: int, e: int) -> list[int]:
    if e - s + 1 <= 1:
        return arr

    pivot = arr[e]
    left = s # pointer for left side

    # Partition: elements smaller than pivot on left side
    for i in range(s, e):
        if arr[i] < pivot:
            tmp = arr[left]
            arr[left] = arr[i]
            arr[i] = tmp
            left += 1

    # Move pivot in-between left & right sides
    arr[e] = arr[left]
    arr[left] = pivot
    
    # Quick sort left side
    quickSort(arr, s, left - 1)

    # Quick sort right side
    quickSort(arr, left + 1, e)

    return arr

# Definition for a pair.
# class Pair:
#     def __init__(self, key: int, value: str):
#         self.key = key
#         self.value = value
class Solution:
    def quickSort(self, pairs: List[Pair]) -> List[Pair]:
        def quickHelper(s, e):
            if e-s+1 <=1:
                return pairs
            
            pivot = pairs[e]
            left = s

            for i in range(s, e):
                if pairs[i].key < pivot.key:
                    pairs[i], pairs[left] = pairs[left], pairs[i]
                    left +=1
            
            pairs[e], pairs[left] = pairs[left], pairs[e]

            quickHelper(s, left-1)
            quickHelper(left+1, e)

        quickHelper(0, len(pairs)-1)
        return pairs

 

Time: O(1)

 

https://youtu.be/H7CNZujkk0k?si=V0lkIbDbFf1BjRTH