Sorting and Comparison Rules
Sorting puts scores in ascending order or files in modification-date order. First decide which key to compare. Also decide whether equal keys should keep their original order.
Follow insertion sort
Like arranging cards in your hand, insert the next item into the already sorted portion on the left.
Start [7, 3, 5, 2]
Insert 3 [3, 7, 5, 2]
Insert 5 [3, 5, 7, 2]
Insert 2 [2, 3, 5, 7]
def insertion_sort(values):
for i in range(1, len(values)):
value = values[i]
j = i - 1
while j >= 0 and values[j] > value:
values[j + 1] = values[j]
j -= 1
values[j + 1] = value
numbers = [7, 3, 5, 2]
insertion_sort(numbers)
print(numbers)
The output is [2, 3, 5, 7]. At each iteration’s start, the portion before i is sorted. Inserting the next value preserves that rule, so the whole list is sorted at the end.
Different costs
- Selection sort: Repeatedly find the smallest remaining value. Comparisons take
O(n²). - Insertion sort: Worst-case time is
O(n²), but the implementation above takesO(n)on already sorted input. - Merge sort: Sort smaller parts, then merge them. Time is
O(n log n); a conventional array implementation usesO(n)extra space. - Quicksort: Partition around a pivot and sort the parts. Average time is
O(n log n), but consistently uneven partitions giveO(n²)worst-case time. - Heapsort: Use heap removal to sort in
O(n log n).
Radix sort groups by digits. Its assumptions differ from comparison sorting, so account for the number of digits and the symbol range too.
Equal keys may still have an order
A stable sort preserves the original order of items with equal keys. The insertion sort above only shifts on >, preserving ties. Python’s sorted() and list.sort() also guarantee stability.
Check your understanding
If > becomes >=, will people with equal scores keep their arrival order?
Show explanation
Not necessarily. Equal values will also shift right, placing the later item before the earlier one. The numbers look identical, but associated information such as names can change order.