Pick a pivot and run partition, pivot itself is at correct position after partitioned.
Run Quick Sort for all numbers on left hand side of pivot
Run Quick Sort for all numbers on right hand side of pivot.
Template
# 912. Sort an Array
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quicksort(l, r):
if l >= r: return
pivot, p = nums[r], l
# paritioning ------------------
for i in range(l, r):
if nums[i] <= pivot:
# numbers on left of pivot should be at p position
nums[p], nums[i] = nums[i], nums[p]
p += 1
# lastly pivot stays at last p
nums[p], nums[r] = pivot, nums[p]
quicksort(l, p-1)
quicksort(p+1, r)
quicksort(0, len(nums)-1)
return nums
Example for a single parition
arr = [1,2,7,3,6,2,5]
l=0, r=6
[1, 2, 7, 3, 6, 2, 5]
i = 0
before p=0 nums=[1, 2, 7, 3, 6, 2, 5]
after p=1 nums=[1, 2, 7, 3, 6, 2, 5]
i = 1
before p=1 nums=[1, 2, 7, 3, 6, 2, 5]
after p=2 nums=[1, 2, 7, 3, 6, 2, 5]
i = 2
before p=2 nums=[1, 2, 7, 3, 6, 2, 5]
after p=2 nums=[1, 2, 7, 3, 6, 2, 5]
i = 3
before p=2 nums=[1, 2, 7, 3, 6, 2, 5]
after p=3 nums=[1, 2, 3, 7, 6, 2, 5]
i = 4
before p=3 nums=[1, 2, 3, 7, 6, 2, 5]
after p=3 nums=[1, 2, 3, 7, 6, 2, 5]
i = 5
before p=3 nums=[1, 2, 3, 7, 6, 2, 5]
after p=4 nums=[1, 2, 3, 2, 6, 7, 5]
Last swap [1, 2, 3, 2, 5, 7, 6]
Quick Select
Similar idea to Quick Sort where we pick pivot and partition recursively. Note that each time a pivot is at correct position we know the following information:
pivot is now at correct position in a sorted array
numbers on the left of pivot are less than pivot
numbers on the right of pivot are greater than pivot
Average Time: O(n)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quickSelect(l,r):
pivot, p = nums[r], l
for i in range(l, r):
if nums[i] <= pivot:
nums[p], nums[i] = nums[i], nums[p]
p += 1
nums[p], nums[r] = pivot, nums[p]
if p == k:
return nums[p]
elif p > k:
return quickSelect(l, p-1)
else:
return quickSelect(p+1, r)
k = len(nums)-k
return quickSelect(0, len(nums)-1)
Quick Sort
Template
Example for a single parition
Quick Select
Similar idea to Quick Sort where we pick pivot and partition recursively. Note that each time a pivot is at correct position we know the following information:
Average Time: O(n)