Lecture 9:

Sorting Algorithms

​

TA: Geonhee Ahn�justamoment@ewhain.net

Insertion Sort in Life

The Great Dalmuti

2

Insertion Sort

3

Sorting Problem

• Input: a list of N numbers
• Output: permutation B[1, …, n] of A such that B[1] ≤ B[2] ≤ … ≤ B[n]
• In other words, a rearranged list of items in the input, such that they monotonically increase (or decrease).
• Example:
• Input:����
• Expected output:

4

Why Sorting?

• Problems become easier once items are in sorted order:
• Finding a median
• Finding the closest pairs
• Binary search
• Identifying statistical outliers�
• Various applications
• Sorting a table by an attribute
• Data compression: sorting finds duplicates.

5

(Human-like) Insertion Sort

• Main idea:
• Start from an empty “sorted list” and a pile of items to sort.
• For each item on the pile, put in the right position in the “sorted list”.
• When there’s no item left in the pile, you are done.

Pile

Sorted list

6

(Human-like) Insertion Sort

• Main idea:
• Start from an empty “sorted list” and a pile of items to sort.
• For each item on the pile, put in the right position in the “sorted list”.
• When there’s no item left in the pile, you are done.

Pile

Sorted list

7

(Human-like) Insertion Sort

• Main idea:
• Start from an empty “sorted list” and a pile of items to sort.
• For each item on the pile, put in the right position in the “sorted list”.
• When there’s no item left in the pile, you are done.

Pile

Sorted list

8

(Human-like) Insertion Sort

• Main idea:
• Start from an empty “sorted list” and a pile of items to sort.
• For each item on the pile, put in the right position in the “sorted list”.
• When there’s no item left in the pile, you are done.

Pile

Sorted list

9

(Human-like) Insertion Sort

• Main idea:
• Start from an empty “sorted list” and a pile of items to sort.
• For each item on the pile, put in the right position in the “sorted list”.
• When there’s no item left in the pile, you are done.

Pile

Sorted list

10

Insertion Sort

• Let’s do this in-place, without using an additional list.
• Start from an empty “sorted list region” and a pile the region of items to sort.
• For each item on the pile in the unsorted region, put in the right position in the “sorted list region”.
• When there’s no item left in the pile unsorted region, you are done.

Sorted

Unsorted

11

Insertion Sort

• Let’s do this in-place, without using an additional list.
• Start from an empty “sorted list region” and a pile the region of items to sort.
• For each item on the pile in the unsorted region, put in the right position in the “sorted list region”.
• When there’s no item left in the pile unsorted region, you are done.

Sorted

Unsorted

12

Insertion Sort

• Let’s do this in-place, without using an additional list.
• Start from an empty “sorted list region” and a pile the region of items to sort.
• For each item on the pile in the unsorted region, put in the right position in the “sorted list region”.
• When there’s no item left in the pile unsorted region, you are done.

Sorted

Unsorted

13

Insertion Sort

• Let’s do this in-place, without using an additional list.
• Start from an empty “sorted list region” and a pile the region of items to sort.
• For each item on the pile in the unsorted region, put in the right position in the “sorted list region”.
• When there’s no item left in the pile unsorted region, you are done.

Sorted

Unsorted

14

Insertion Sort

• Let’s do this in-place, without using an additional list.
• Start from an empty “sorted list region” and a pile the region of items to sort.
• For each item on the pile in the unsorted region, put in the right position in the “sorted list region”.
• When there’s no item left in the pile unsorted region, you are done.

Sorted

Unsorted

Sorted

15

Insertion Sort: Implementation

def insertion_sort(list):

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

key = list[i]

j = i - 1

while j >=0 and key < list[j]:

list[j+1] = list[j]

j -= 1

list[j+1] = key

Sorted

i

key

j

16

Time Complexity

• At the i-th iteration, its inner loop (while) does:
• Find the location to put the next item among i items,
• Shift all items on the right side by 1,
• Put the target item at the found position.�
• How many iterations?�
• Overall complexity?�
• If the input list is almost sorted, each iteration will be done by ≈O(1), so overall time complexity will be ≈O(N).

?

O(N)

O(N)

O(1)

Complexity?

O(log N) if binary search used.

O(N)

O(N²)

17

Selection Sort

18

Selection Sort

• Main idea: the opposite of insertion sort!
• Instead of putting the next item in the right place,
• Find the smallest item in the unsorted region, and
• Swap it with the item in its right position.

Sorted

Unsorted

Find the smallest among unsorted ones.

The smallest is already in the target place 😀

19

Selection Sort

• Main idea: the opposite of insertion sort!
• Instead of putting the next item in the right place,
• Find the smallest item in the unsorted region, and
• Swap it with the item in its right position.

Sorted

Unsorted

Find the smallest among unsorted ones.

Swap it with the one at the target position.

20

Selection Sort

• Main idea: the opposite of insertion sort!
• Instead of putting the next item in the right place,
• Find the smallest item in the unsorted region, and
• Swap it with the item in its right position.

Sorted

Unsorted

Find the smallest among unsorted ones.

Swap it with the one at the target position.

21

Selection Sort

• Main idea: the opposite of insertion sort!
• Instead of putting the next item in the right place,
• Find the smallest item in the unsorted region, and
• Swap it with the item in its right position.

Sorted

Unsorted

Find the smallest among unsorted ones.

Swap it with the one at the target position.

Repeat until there is no item left in the unsorted region!

22

Selection Sort: Implementation

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 recursion?

23

Time Complexity

• At the i-th iteration, its inner loop (for) does:
• Find the smallest items among N - i unsorted items,
• Swap it with the item at the next position.�
• How many iterations?�
• Overall complexity?�
• No benefit even though the input list is almost sorted.
• When we find the next smallest item, we do not assume the remaining list is sorted.

?

O(N)

O(1)

Complexity?

O(N)

O(N²)

24

Merge Sort

25

Announcement & Tentative Schedule

• 10/30 - Quiz 2
• 11/3 - 11/14: Priority Queue, Heap
• 11/17 - Quiz 3
• 11/20-12/4 : Hash Table 2, Graph
• 12/8: Quiz 4

26

Motivation

• Insertion sort and selection sort work but too slow.
• Time complexity is O(N²).
• Does not matter when handling small data, but we want to handle big data!�
• Any better idea?
• Divide and conquer!

27

Merge Sort

• Main idea:
• Divide the whole list into two sub-lists.
• Sort the left and right sublists separately.
• Merge the two sorted sublists into a single sorted one.

Sort

Sort

Merge

28

Merge Sort

• Further breakdown: each sublist is also sorted in a similar way!

Okay, dividing is easy!

Sorting each separately is also easy, as they have just a single item in the end.

29

Merge Sort

• Further breakdown: each sublist is also sorted in a similar way!

What about merging?!

30

Merge Sort

• At each step, the only non-trivial task is merging two sorted arrays into a single sorted array.

• First trial with brute force:
• Concatenate the two list
• Sort the entire list with insertion (or selection) sort.
• Time complexity?

• 1st split: 2 × (N/2)², 2st split: 4 × (N/4)², 3rd split: 8 × (N/8)², …
• In total, O(N²). No benefit from directly sorting entire matrix at once.

31

Merge Sort

• So, we need more efficient merging, taking advantage of the fact that the two sublists are already sorted.

The first (smallest) item must be either the smallest item in the left sublist or the smallest one in the right sublist.

-6

32

Merge Sort

• Then, what about the next one?

The second smallest item must be either the smallest item in the left sublist or the second smallest one in the right sublist (since -6 was already used).

-2

33

Merge Sort

• In a similar way, we choose the smaller one between the smallest remaining items in each list at a time, until both lists are completely consumed.

0

4

5

7

9

10

Now, both sublists are all used!

34

Merge Sort: Time Complexity

• Time complexity of this merging step?
• At each time we fill the output, we
• Compare two elements once → O(1)
• Write the small one → O(1)
• Move one pointer on the selected side → O(1)
• How many times do we repeat this?
• Same as the output list size!
• 1st split: 2 × (N/2), 2nd split: 4 × (N/4), … → O(N)

0

4

5

7

9

10

35

Merge Sort: Time Complexity

• How many steps do we have?
• Same as the height of this tree:

• So, overall time complexity is:

O(log N)

O(N log N)

36

Merge Sort: Implementation

def merge_sort(list):

if len(list) > 1:

mid = len(list) // 2 # round down

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.

37

Merge Sort vs. Insertion Sort

• How different the speed is, between O(N²) vs. O(N log N)?

N

N

Time (sec)

38

Can we do better?

• Insertion / Selection sort takes O(N²).
• Merge sort takes O(N log N).
• Can we do better?

What is the best possible time complexity for sorting problem?

Then, can we sort in O(N)?

O(N), because we need O(N) to read the input list anyway.

Yes, if we have some additional conditions.

(It was proved that O(N log N) is the best for comparison-based sorting algorithms.)

39

Linear-Time Sorting: O(n)

40

Counting Sort

• A linear-time sorting algorithm under the condition that the input elements are always integers between 0 and k.
• Example:

41

Counting Sort

• Intuitive example: N = 7, k = 7

Stable sort: the original order is preserved for items with the same key.

5

7

2

5

1

5

7

7

5

1

5

5

7

2

42

Counting Sort

• Algorithm�
• Reading the entire input list, increase the number of occurrences of each key.����
• Take cumulative sum of this counts.�→ This is the ending index of each number in the sorted output.

43

Counting Sort

• Algorithm�
• Read the input list once again from backward,
• Subtract the target index by 1,
• Put the element there, and move on.

Why backward?

→ For stable sort!

4

5

6

7

1

2

3

5

44

Counting Sort: Implementation

def counting_sort(list):

output = [0] * (len(list))

count = [0] * (max(list) + 1)

� for i in range(len(list)):

count[list[i]] += 1

� for i in range(1, len(count)):

count[i] += count[i-1]

� for i in range(len(list)):

j = len(list) - 1 - i

count[list[j]] -= 1

index = count[list[j]]

output[index] = list[j]

​

return output

Count occurrences of each key.

Cumulative sum

Locate each element at the right position in the output.

Time complexity?

O(N)

O(k)

O(N)

Overall, O(N + k).

If k ≤ N, counting sort runs in linear time on the input size (N).

45

Sorting in Reality

• What sorting algorithm is used in Python library?
• Timsort (2002): a hybrid sorting algorithm (merge sort + insertion sort)
• A variant of merge sort (divide and conquer)
• When a sublist becomes smaller than some threshold, it is sorted using insertion sort.
• Insertion sort is faster than merge sort for a small list.�
• If your data is small enough, insertion/selection sort may work okay.
• Otherwise, merge sort or quick sort is recommended.
• You may consider a linear-time sorting if your key is integer within a reasonable range. However, it may be hard to take advantage unless the dataset is really huge, and you implement efficiently.

46

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?

47

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)

48

Homework 3

49

Homework 4

50

Homework 5

51