Merge Sort
LC 148: Sort a Linked List
Use fast and slow pointers to divide into two halves, break in the middle, recursively sort each half, and finally merge the two sorted linked lists in ascending order. Boundary conditions: head==None or head.next==None.
LC 23. Merge k Sorted Lists
Pay attention to edge cases.
Quick Sort
Using an element of the array (usually the first element) as the pivot, move all elements smaller than the pivot to its left, and all elements larger than the pivot to its right.
Python Template
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def partition(nums, left, right):
pivot = nums[left] # Initialize a data to be compared
i,j = left, right
while(i < j):
while(i<j and nums[j]>=pivot): # Search from right to left until a number smaller than pivot is found
j-=1
nums[i] = nums[j] # Put the smaller number to the left
while(i<j and nums[i]<=pivot): # Search from left to right until a number larger than pivot is found
i+=1
nums[j] = nums[i] # Put the larger number to the right
# Loop ends, i equals j
nums[i] = pivot # Put the data to be compared in its final position
return i # Return the final position of the data to be compared
def quickSort(self, nums, low, high):
if low<high:
pivot=self.partition(nums, low, high)
self.quickSort(nums,low, pivot-1)
self.quickSort(nums, pivot+1, high)
|
215 Kth Largest Element in an Array
Video Explanation
Expected linear selection algorithm.
When the function returns, the (m+1)-th smallest element is exactly at index m. And all elements smaller than it are to its left, and all elements larger than it are to its right.
Avoid timeout: Three-way partitioning.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
def three_way_partition(nums, low, high):
# Randomly select a pivot element and swap it to the leftmost end (to avoid worst-case scenarios)
rand_pivot = random.randint(low, high)
nums[low], nums[rand_pivot] = nums[rand_pivot], nums[low]
pivot = nums[low]
# Initialize three pointers:
# [low..lt] < pivot
# [lt+1..i) == pivot
# [gt..high] > pivot
lt = low # Right boundary of the left partition (last position < pivot)
gt = high + 1 # Left boundary of the right partition (first position > pivot)
i = low + 1 # Current scan pointer
while i < gt:
if nums[i] < pivot:
lt += 1
nums[i], nums[lt] = nums[lt], nums[i]
i += 1
elif nums[i] > pivot:
gt -= 1
nums[i], nums[gt] = nums[gt], nums[i]
else:
i += 1
# Swap the pivot element to the beginning of the middle partition
nums[low], nums[lt] = nums[lt], nums[low]
lt -= 1 # Now [low..lt] < pivot, [lt+1..gt-1] == pivot, [gt..high] > pivot
# Return the right boundary of the left partition and the left boundary of the right partition
return lt, gt
|
Recursive function
1
2
3
4
5
6
7
8
9
10
11
| def quickSort(self, nums, low, high,m):
if low<high:
# Call the three-way partition template
lt, gt = self.partition(nums, low, high)
# Determine which partition the target position is in
if m <= lt: # Target is in the left partition
return self.quickSort(nums, low, lt, m)
elif m >= gt: # Target is in the right partition
return self.quickSort(nums, gt, high, m)
else: # Target is in the middle partition (direct hit)
return nums[m]
|