CS61B Guide
Search…
Object Oriented Programming
Abstract Data Types
Sorting
Sorting
For more information about specific sorting algorithms covered in 61B, see my guide on sorting that covers all of the sorts in far greater detail 🙂
Why sort?
- It makes searching for a specific value much faster (e.g. binary search). Typically, searching through an unsorted list requires a full scan (​ runtime).
- It's easy to see if two items in list are equal: just compare to see if any neighboring values are the same.
Properties of a Sorting Algorithm
A sorting algorithm changes a sequence based on a total order. A total order is:
- Total: All items can be compared with one another
- Reflexive: An item can be compared to itself
- Antisymmetric: x <= y AND y <= x IFF y == x
- Transitive: If x <= y and y <= z, then x must be <= z
A sorting algorithm could be stable if it does not change relative order of equivalent entries. For example, if Bob and I both owned Toyota Corollas, and the list of cars were sorted by model, if Bob's car came before mine originally it must also come before mine in the sorted list after a stable sort.
​
Sorting Algorithm Classifications
- Internal sort: Keeps all data in primary memory
- vs. External sort: Processes data in batches, then merges them together at the end
- Comparison-based sort: The only thing we know about keys are their relative orders
- Radix sort: Uses information other than keys
- Insertion sort: Insert items at their appropriate positions one at a time
- Selection sort: Chooses items and places them in order
Sorting in Java
Java automatically chooses the best sorting algorithm for a given list if you call the
Arrays.sort method.1
String[] x = new String[] {"Vat", "Bat", "Cat"};
2
​
3
Arrays.sort(x); // mutates x into Bat, Cat, Vat
4
Arrays.sort(x, Collections.reverseOrder()); // mutates x into Vat, Cat, Bat
5
Arrays.sort(x, 0, 2) // sorts the first two elements, leaving the rest unchanged (Cat, Vat, Bat)
Copied!
Inversions
Inversions are used as a measure for how sorted a list is. For every two elements that are swapped compared to a sorted list, we add one inversion.
- As an example, if
1 2 3 4 5is a sorted list,1 4 3 2 5would have one inversion (4and2are swapped). - 0 inversions mean a list is perfectly sorted.
- In the worst case, a reversed list will haveinversions.