This week we did a practical study into different sorting algorithms and their time complexities. I really like sorting algorithms. I don’t know why. It was a good week.

Sorting algorithms take an array of items (`[10, 8, 5, 15, 23, 20]`

) and turn it into a sorted array (`[5, 8, 10, 15, 20, 23]`

). There are a bunch of different sorting algorithms. Some of them I have mentioned before (Bubble sort and Quicksort), so I’ll skip them for now. First up is Insertion sort, which is really cool.

The idea is that you keep an array of the sorted items, and then insert each item in the unsorted list into it’s proper place. Here’s an example:

Starting with [10, 8, 5, 15, 23, 20], we have the following steps: [10, , , , , ] [8, 10, , , , ] [5, 8, 10, , , ] [5, 8, 10, 15, , ] [5, 8, 10, 15, 23, ] [5, 8, 10, 15, 20, 23] —-

You can try this out with a deck of cards. Look at each unsorted card, and slip it into the appropriate sorted spot. Insertion sort’s complexity is O(n^2) footnote:[O(something) means that as `n`

, the number of items in the list, grows, the time the sorting algorithm takes is asymptotically proportional to `something`

. For more information, see link:https://setupminimal.github.io/blog/2016/09/18/Computer-Science-Week–3-The-Worst-Possible-Time.html[my previous computer science post].] at worst, but it has a few interesting properties. Insertion sort is fast for small lists. For anything less than about 12 items, it is the fastest sort. Insertion sort is also faster when a list is almost sorted. In the best case, Insertion sort is O(n), which is the fastest possible.

Shell sort uses the fact that Insertion sort works faster on almost-sorted lists to sort big lists more quickly. The idea behind Shell sort is that you pick different *strides*, and do an insertion sort on every *strideth* item. The first few passes get the list into roughly-sorted order, and then a final insertion sort is fast. Depending on how you pick your strides, Shell sort can have a bunch of different complexities. I don’t know enough (and the Professor glossed over it) to derive the complexity of Shell sort, but I can tell you that when your strides are powers of 2 minus 1 (`a_n = (a_(n-1) + 1) * 2 - 1 = n ^ 2 - 1`

), the complexity is O(n^1.5).

Here’s an example, with strides 3, 2, and 1:

[40, 88, 10, 8, 5, 15, 23, 20]

First, with stride = 3: [8, 88, 10, 23, 5, 15, 40, 20] ^ ^ ^ switch

[8, 5, 10, 23, 20, 15, 40, 88] ^ ^ ^ switch

[8, 5, 10, 23, 20, 15, 40, 88] ^ ^ already sorted

Now stride = 2: [8, 5, 10, 23, 20, 15, 40, 88] ^ ^ ^ ^ already sorted

[8, 5, 10, 15, 20, 23, 40, 88] ^ ^ ^ ^ switch

Now stride = 1: (This is just insertion sort) [5, 8, 10, 15, 20, 23, 40, 88] ^ ^ ^ ^ ^ ^ ^ ^ —-

Note that even though we had to do more steps, each step was faster because insertion sort is fast for small groups, and fast for almost-sorted groups.

The final sorting algorithm we talked about was Selection sort, Bubble sort’s pretty cousin. With this sort, you maintain an array of already sorted items. Then, you search through the list for the biggest item, and tack that onto the sorted array.

[8, 5, 10, 15, 23, 20] [8, 5, 10, 15, 20 | 23] [8, 5, 10, 15 | 20, 23] [8, 5, 10 | 15, 20, 23] [8, 5 | 10, 15, 20, 23] [5 | 8, 10, 15, 20, 23] [5, 8, 10, 15, 20, 23] —-

This sorting algorithm is always O(n**2) - but it’s still faster than Bubble sort, which has the same complexity, because it performs fewer swaps of numbers.

That’s all for this week. I hope you learned something, and I’m going to point once again to link:https://www.youtube.com/watch?v=kPRA0W1kECg[that video that visualizes sorting algorithms]. Now that you know how a few more work, it might be fun to check it out again.