sorting = arranging a collection of items in order
e.g. arrays, linked lists, files
typically, sorting is done in ascending or descending order
typically, items are sorted based on an ordering relation of that property
e.g. numerically, alphabetically
we want a function sort(ordered collection, lo, hi); that sorts an ordered collection of items from index lo to index hi
e.g. to sort an array a[N], we would call sort(a, 0, N-1)
preconditions:
lo, hi are valid indexses of the collection (i.e., 0 ≤ lo < hi ≤ N-1)
a[lo..hi] contains defined values of type Item
postconditions:
a[lo..hi] contains the same set of values as before the sort
for each i in lo..hi-1, we have that a[i] ≤ a[i + 1]
in-place sort = sorting algorithms that directly modifies the original collection to sort (no copies of the array made etc. that cost extra memory)
stable sort = a sorting algorithm that maintains the order of duplicate values
given that x == y, if x preceeds y in an unsorted list, x also preceeds y in a sorted list
adaptive sort = performance is affected by the actual values of items
i.e., best, average and worse cast performance differs
e.g. bubble sort has $\Omega$(n) and O(n^2)
we focus on three main cases: how quickly does our algorithm sort a collection in…