← Blogs

Sorting

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]