CS 161 Homework 3

CS161

Scarlett Zhang 66108402

R-9.1

Bubble-sort is stable.
Heap-sort is not stable.
Merge-sort is stable.
Quick-sort (3 way) is not stable.
Quick-sort (2 way, in place) is stable. Because it only swap items when there's an inequality.

R-9.5

When the array is already sorted, and we choose the first element as the pivot, and try to select the largest number in this array, the complexity reaches $n^2$.
Because when we choose the smallest number as the pivot, we only sort this one element after comparing it with other elements, then we choose the second smallest element which is also the smallest among the unsorted part of the array. So the same thing happens repeatedly until we find the last element on the right side. Every recursion the input size just become 1 less than the previous recursion, and all elements need to be compared with the smallest number.

C-9.2

Create $2n$ buckets, bucket-sort input list A ($O(n)$), and then bucket-sort input B using the same $2n$ buckets($O(n)$). Finally, check all buckets to see how many of them have more than one integer inside ($O(n)$). Those buckets' indices are duplicate numbers. The complexity as a whole is $O(n)$.

C-9.4

def sortWithList(l):
pair_result = []
for listnum in range(len(l)):
    for e in l[listnum]:
        pair_result.append((e,listnum))
# O(n) for this nested loop, the goal is to extract the listnum
# according to the question, we know N-1
# now construct a bucket sort with N-1 buckets
N = 10
buckets_round1 = [ [] for i in range(N)]
pair_container_round1=[]
buckets_round2 = [ [] for i in range(len(l))]
pair_container_round2=[ [] for i in range(len(l))]
for p in pair_result:
    buckets_round1[p[0]].append(p)
    # sort with lower priority: the value
    # above is O(n) 
for i in range(N):
    for x in buckets_round1[i]:
        pair_container_round1.append(x)
for p in pair_container_round1:
    buckets_round2[p[1]].append(p)
for i in range(len(l)):
    for x in buckets_round2[i]:
        pair_container_round2[i].append(x[0])
return pair_container_round2

print(sortWithList([[4,3,6],[7,6,3],[2,9,6]]))
> [[3, 4, 6], [3, 6, 7], [2, 6, 9]]