Sequence Implementations

Cont. from last time

Dynamic Array Sequence

• Can we improve on the (regular) array sequence, which requires $O(n)$ to add new elements?
• Yes! Over-allocate additional space when you request space for the array
• If we do it right, we can guarantee that any sequence of $n$ insertions only takes $O(n)$ time, and takes $O(1)$ time per insertion on average
• This is called amortized constant time, because the cost of the operation is amortized across many applications of the operation
• Our strategy: allocate extra space in proportion to the size of the array being stored (any fraction works for the amortized bound)
• Why? Because $O(n)$ additional space ensures that a linear number of insertions must occur before an insertion will overflow the allocation
• Often, implementations will allocate double the amount of space needed to store the current array, known as table doubling
• When the length of the array becomes sufficiently small, we reallocate, making sure there remains a linear fraction of unused allocated space when we rebuild
• This guarantees that $\Omega(n)$ sequential dynamic operations must occur before the next time we need to reallocate memory

Exercises

• Next pointer of last node of linked list points to earlier node in list, creating a cycle. Given a pointer to the head of the list (without knowing its size), describe a linear-time algorithm to find the number of nodes in the cycle. Use only constant additional space outside the original linked list.
• Given a data structure implementing the Sequence interface, use it to implement the Set interface. Doesn't need to be efficient.

Faster Sets

• We've reduced the Set interface to the Sequence Interface, or simulated one with the other. But everything takes linear time.
• To do better, we can store our items in a sorted array, so we can use binary search to find keys and support Order operations

Sorting

• Incremental: maintain and grow a sorted subset of items until all items are sorted
• Selection sort maintains and grows a subset of the largest $i$ items in sorted order, while insertion does the first $i$ items

Selection Sort

• Already sorted smallest items into sub-array A[:i], so repeatedly scan rest of array for smallest item not yet sorted, then swap with item A[i]
• Can require $\Omega(n^2)$ comparisons, worst case $O(n)$ swaps

Insertion Sort

• Already sorted sub-array A[:i], so repeatedly swap item A[i] with item to its left until the left item is no larger than A[i]
• Can require $\Omega(n^2)$ comparisons, worst case $\Omega(n^2)$ swaps

In-place and Stability

• In-place: can be implemented using at most a constant amount of additional space
• Stable: items having the same value will appear in the sort in the same order as they appeared in the input array

Merge Sort

• Recursively sorts left and right half of array, then merges the two halves in linear time

• Recurrence relation: $T(n) = 2T(n/2) + \Theta(n)$, which solves to $T(n) = \Theta(n \log n)$

  • $\log n$ grows slower than any polynomial $n^{\epsilon}$ for $\epsilon > 0$
• Not in-place: uses a linear amount of temporary storage
• Whether or not it's stable depends on how an implementation breaks ties when merging

Build a Sorted Array

• Preprocessing: spend extra time building the data structure to speed up order queries later