# Eboard 24: Sorting

You are being recorded and transcribed.

Approximate overview

• Check in on Wednesday’s class
• Some notes on sorting
• Testing sorting algorithms
• Loop invariants

## Preliminaries

• Registration preview

### Upcoming work

• Friday, 2024-03-15, 11pm, Third set of LAs.
• Mostly posted.
• Let me know if any look wrong.
• Let me know if you’d like to see any others posted.
• Grading is still on my priority queue, near the front.

### Tokens

Cultural

• Friday at 4pm in the Global Living Room. Middle of Everywhere.
• I don’t know whether or not that’s happening.

Peer

Wellness

Misc

### Spring Break PSA

• You are awesome. Please take care of yourselves.
• And don’t get me fired for sharing information with you.

## Check in on Wednesday

What did you learn?

• Merge sort.
• Merge algorithm: Merge two sorted lists (or subarrays)
• Merge sort - If the list has more than one element, divide the unsorted list in half, sort the two halves, merge them together.
• Can I merge in place (e.g., [1 ,4, 6, 9, 2, 3, 5, 8])?
• Nope. I need to make a helper array to copy things into.
• This is a disadvantage of merge sort: It requires O(n) extra space.
• Do I have to use merge sort when I sort each subarray?
• Nope.
• How do you prove it correct?
• Experimentally, we run tests
• We could do a proof. With invariants.
• Is merge sort stable?
• Stable: If there are two “equal” elements, they maintain their order. (That may have been in the reading.)
• No: It depends a bit on how you merge.
• Can we decide on an approach that maintains stability? Yes! When we merge, always take the element from the left array first.

## Some notes on sorting

• Stability
• We all sort all the time.
• MSort: Divide the cards into two piles: Sorted and Unprocessed. For each card in unprocessed, put it into the right place in sorted.
• ASort: Similar, with a probabilistic (ML-based) approach for finding the right location.
• Insertion sort
• Analysis of insertion sort (incorrect)
• We have to insert n cards from unprocessed list into the sorted list.
• Finding the right location takes O(logn) time because we can use binary search.
• Inserting it into that position is constant time.
• This algorithm is O(nlogn).
• Why is this incorrect? (Hint: It may be O(nlogn) in the physical world, but not in the computer world.)
• If the data are stored in an array, it will take O(n) to insert, not O(1) because you have to shift stuff over to make room.
• If the data are stored in a link list, it only takes O(1) to insert once you’ve found the spot, but be can’t use binary search on lists, since binary search requires quick access based on index.
• Analysis: O(n^2) for arrays because O(n) to insert.
• Analysis: O(n^2) for lists because O(n) to find.
• Reminder: Once you’ve correctly analyzed an algorithm, you have two questions to ask:
• Can I do better?
• If not: Can I prove that I can’t do better?
• Detour: For the “can I prove”, Travelling Salescritter Problem
• Given a set of n cities, find the shortest path connecting them all.
• Easy solution: Make a list of all the paths, take the shortest.
• Unfortunately, there are O(n!) paths, which grows way too quickly.
• In 301, you’ll get to consider whether a sorting algorithm can be faster than O(nlogn). (Preview: Not for a compare/swap algorithm.)
• In 341, you’ll get to explore questions like TSP.
• For insertion sort’s “can I do better”
• Design a different algorithm
• Design a new data structure, one that has both quick insertion and quick searching.
• A better data structure: The binary search tree
• A binary tree is a structure in which you have a node (with a value), left subtree, and right subtree.
• Usually the left subtree has values less than the node and the right subtree has values greater than the node.
• Both left and right subtrees have the same property.
• If the tree is mostly balanced (that is, we have left and right subchildren at most levels; the two subtrees are about the same size ), the number of levels is O(logn).
• Search is O(logn)
• Insert is O(logn)
• Maintaining the property is hard.

## Testing sorting algorithms

You’ve written a sorting algorithm. Proofs are hard. You want tests. What kind of “write lots of tests” algorithm would you write?

• Systematically
• Random

Systematically

• Use for loops to build arrays of different sizes
• For each size array

Random

• Use a for loop to build arrays of different sizes
• Sort each
• And make sure it’s in order AND a permutation of the original

Sam’s Sorting algorithm (which gives you an array in order)

 public static T samSort(T[] values, Comparator order) { for (int i = 1; i < values.length; i++) { values[i] = values[0]; } } // samSort `

More ideas