Lecture 13:�Problem Solving (Sorting)

Announcement

• Quiz 3 – Next week (20%)
• Sorting
• Level : Leetcode easy
• 1 problem : Similar with our homework
• 1 problem : New
• Similar with Quiz 1
• Evaluation: Test Code � (if pass🡪 get the full score, otherwise 🡪 get 0 score)

2

Homework 1

def selection_sort(list):

for i in range(len(list)):

smallest = i

for j in range(i+1, len(list)):

if list[j] < list[smallest]:

smallest = j

list[i], list[smallest] = list[smallest], list[i]

Sorted

i

smallest

swap

Q. Can you implement this with selection sort with recursion?

3

Homework 1 – Solution

Def SelectionSort(A[], i): # i = last index of the sorted region

​

1. Base case: �if i == len(A)-1:� return A
2. Recursion�for j in range(j+1, len(A)-1):� if A[i] > A[j]:� A[i], A[j] = A[j], A[i]�SelectionSort(A[], i+1)

Time complexity : O(n^2)

​

4

Homework 2

def merge_sort(list):

if len(list) > 1:

mid = len(list) // 2

left = list[:mid]

right = list[mid:]

​

merge_sort(left)

merge_sort(right)

​

# TODO(students): merge left & right in the list

“else” for this is the base case, where the recursive calls are done.

We skip it here, since there’s no action item in the base case.

Q. Please implement merge sort. (# TODO section below)

5

Homework 2 – Solution

6

Homework 3

7

Homework 3 – Solution

1. Counting Sort: Time complexity O(n), Space complexity O(n)�

​

• Allocate value to the new array within new index num[i]-min(num):�Time complexity O(n), Space complexity O(n)�
• Compare the total sum:�Time complexity O(n), space complexity O(1)

8

Homework 4

9

Homework 4 – Solution

nums = [3, 30, 34, 5]���

• make every element as the string: nums = [“3”, “30”, “34”, “5”]

​

• Define new compare function�def compare(n1,n2):� if int(n1+n2) > int(n2+n1)� return n1� else: � return n2�
• Use Merge Sort using new compare function

Time complexity : O(nlog(n))

​

10

Homework 5

11

Homework 5 – Solution

​

​

​

​

1. Sort intervals by its starting value��
2. Merge them sequentially��if last_end< start:� end ←max(last_end, end)

12