Lecture 18:

Sorting, Part 3

CS 136: Spring 2024

Katie Keith

Record on Zoom

• Welcome prospective students
• Lab 5 due Monday or Tuesday
• Lab 6 next week: No starter code!
• Optional Midterm Corrections due Monday April 14 at 10pm. Submit on Gradescope.
• TA eval form (Due April 18) : https://forms.gle/sbqCGVLAFnhUQ4i39

​

📣 Announcements

📣 Announcements

• Merge Sort
• Implement
• Big-O
• Quick Sort (pseudocode)
• Wrap-Up Sorting

🎯 Today’s Learning Objectives

📚Readings

• Sedgewick and Wayne. Algorithms. Section 2.2
• Sedgewick and Wayne. Algorithms. Section 2.3

Sorting Algorithms

Merge Sort

Invented by John von Neumann in 1945.

Divide & Conquer

Merge sort uses the divide and conquer paradigm, a paradigm that is helpful for many different algorithms in computer science.

• Divide: Recursively break down problems into smaller, more manageable subproblems.
• Conquer: Combine the solutions to these subproblems to solve the original problem.

Merge Sort: Divide Operation

Recursively divide the unsorted array into two different arrays until each smaller array is a single element (base case).

…

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

Two sorted subarrays

7

8

2

9

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

Compare (smallest/

left-most elements)

7

8

2

9

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

7

8

9

2

New merged & sorted array

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

7

8

9

2

New merged & sorted array

Compare (smallest/

left-most elements)

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

8

9

2

7

New merged & sorted array

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

8

9

2

7

New merged & sorted array

Compare (smallest/

left-most elements)

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

8

9

2

7

New merged & sorted array

Compare (smallest/

left-most elements)

Merge Sort: Merge operation

Recursively merge: compare the smallest element in the left array with the smallest element in the right array and repeat.

Do so until there is only one large sorted array remaining.

8

New merged & sorted array

2

7

9

Example

GIF credit: Wikipedia

MergeSort.java

💻

int i = lo;

int j = mid+1;

for (int k = lo; k <= hi; k++) {

if (i > mid) a[k] = aux[j++];

else if (j > hi) a[k] = aux[i++];

else if (aux[j]< aux[i]) a[k] = aux[j++];

else a[k] = aux[i++];

}

​

The chunk of code below is the important part of our merge operation for merge sort.

​

Use pen & paper to track how the example array a (above) changes as i, j and k change in the code.

a

aux

lo=0

mid=1

hi=3

Two sorted subarrays from previous steps

lo, mid, and hi designate the boundaries of the sorted subarrays

💡Think-pair-share

• Merge Sort
• Implement
• Big-O
• Quick Sort (pseudocode)
• Wrap-Up Sorting

✅

🎯 Today’s Learning Objectives

Sorting Algorithms

Merge-Sort Time & Space Big-O

Board work

• Merge Sort
• Implement
• Big-O
• Quick Sort (pseudocode)
• Wrap-Up Sorting

✅

✅

✅

🎯 Today’s Learning Objectives

Sorting Algorithms

Quicksort

Invented by Tony Hoare in 1959.

Quicksort overview

Overview:

• Like Mergesort, Quicksort also uses the “divide and conquer” paradigm and is applied recursively.
• Like Insertion Sort, Quicksort sorts an array in-place.
• Randomized algorithm

Divide:

• Randomly choose a pivot element.
• Swap elements (possibly including pivot) so those with values less than the pivot come before it, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way

Conquer:

• Recursively sort the two new partitions

Quick Sort example

Key

Filled black square = pivot element

Red outline = Positions of left pointers (i) and right pointers(j)

Black outline = Elements that are already correctly sorted

​

Quick Sort pseudocode

Shuffle the array

Recursively:

1. Pick an element randomly in one of the unsorted sub-ranges, with index called pivot
2. Partition the sub-range with the goal that elements smaller than array[pivot] are placed left of this element and elements larger placed right
1. Create a left pointer (i) with at the beginning of the sub-range (i < pivot )
2. Create a right pointer (j) with at the end of the sub-range (j > pivot)
3. Infinite loop
1. If the pointers indices cross (i >= j), then break
2. Else if array[j] > array[pivot], then j--
3. Else if array[i] < array[pivot], then i++
4. Else swap array[j] and array[i]

• Merge Sort
• Implement
• Big-O
• Quick Sort (pseudocode)
• Wrap-Up Sorting

✅

✅

✅

✅

🎯 Today’s Learning Objectives

Sorting Algorithms: Conclusion

Sorting Algorithms: Conclusion

Different partitioning strategies can change this

What algorithm for Python’s .sort() method?

Sorting algorithms as music

Start at :28

• Merge Sort
• Implement
• Big-O
• Quick Sort (pseudocode)
• Wrap-Up Sorting

✅

✅

✅

✅

✅

🎯 Today’s Learning Objectives