This week we covered chapters 13 and 14 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link). I’ve been coding along in Python on my Github.
Our topics today were Quicksort and linked lists.
Recursive Algorithms for Speed
- There are many ways to choose the pivot during partitioning (e.g., first, last, middle, random). Ideally you want a pivot that evenly partitions the list.
- An important aspect of partitioning: After partitioning, the pivot is now in its proper place.
- I’m sure this can be brushed aside because Big O is about magnitude, but technically Quicksort is O(N log_2 N). It’s base-two because you make two sublists and sort them.
- Regarding the worst-case for Quicksort (i.e., an already sorted list), there are heuristics for this to make it O(N). Count the number of swaps during the partition; if it’s zero, you’re done. Another one is to do a check to see if the list is already sorted, which is O(N).
- I’d never heard of Quickselect before; Houston hadn’t either. Basically you only keep looking in areas of the array you care about — ignore everything else, as there’s no need to process it.
- The Big O of Quickselect being O(N) I think is a geometric series — N + N/2 + N/4 + N/8 + …
- Merge sort is useful for sorting linked lists (i.e., no locality of reference where the N+1th element is one cell to the right of the Nth element).
- Houston spent more time than he planned coding up the exercises in this section.
- Necklace: the last node of a linked list points to the first
- Something that helped Dennis understand Quicksort was this dance video.
Node-Based Data Structures
- One of the most powerful attributes of linked lists is the O(1) insertion and deletion — no need to shift elements.
- Dennis shared an analogy… Arrays are like contiguous seats in a movie theater.
- I think the author buried the lede about doubly-linked lists being good for queues and stacks. So basically, linked lists as just lists aren’t super useful, but as specific types of lists they are.
- Exercise 4: My first approach is to build a new list by iterating over the original one backward. Then return the pointer to the new list’s head node. Alternatively, you could use an array/list to make note of all the pointers, then iterate over that array backward to rewrite the pointers in the original list. (I like the book’s simpler approach of only needing to keep track of previous, current, and next.)
- Houston thought about using recursion for Exercise 4 without much success.
- Exercise 5: I didn’t know how to do this one. The trick is you copy the next node into yourself and link yourself to the node that comes after it then delete the next node.
- I learned that Python has no bottom-tested loops (e.g., do-while).