Learning Algorithms

Chapter 5. Sorting Without a Hat

In this chapter, you will learn:

• How comparison-based sorting algorithms require two fundamental operations:

  • less(i,j) determines whether A[i] < A[j].

  • swap(i,j) swaps the contents of A[i] and A[j].

• How to provide a comparator function when sorting; for example, you can sort integers or string values in descending order. The comparator function can also sort complex data structures with no default ordering; for example, it is not clear how to sort a collection of two-dimensional (x, y) points.

• How to identify inefficient O(N²) sorting algorithms, such as Insertion Sort and Selection Sort, from the structure of their code.

• Recursion, where a function can call itself. This fundamental computer science concept forms the basis of a divide-and-conquer strategy for solving problems.

• How Merge Sort and Quicksort can sort an array of N values in O(N log N) using divide and conquer. How Heap Sort also guarantees O(N log N).

• How Tim Sort combines Insertion Sort and functionality from Merge Sort to implement Python’s default sorting algorithm in guaranteed O(N log N).

In this chapter, I present algorithms that rearrange the N values in an array so they are in ascending order. Organizing a collection of values in sorted order is an essential first step to improve the efficiency of many programs. Sorting is also necessary for many real-world applications, such as printing staff directories for a company with the names and phone numbers ...