# A "Feild" Guide to Programming with C++

Introductory programming notes by Henry Feild# Chapter 11: Sorting

## Important takeaways

- there are lots of ways to sort a list of data, but some are faster then others
- some worst case O(n
^{2}) sorting algorithms:- bubble sort
- insertion sort
- selection sort
- quick sort (average case is O(n log
_{2}n))

- a worst case O(n log
_{2}n) sort:- merge sort

- many other sorts exist that are not discussed here!

## Contents

## Sorting lists

We saw that sorting lists of data makes searching them more efficient. In this topic, we'll go over some of the ways to sort arbitrary data—strings, ints, chars, your own custom struct and class types, etc. Just as an example, we'll use this short list of numbers when explaining several different sorting algorithms:

5 | 10 | 3 | 20 | 8 |

## Bubble sort

Bubble sort is one of the simplest sorts. It's also among the most expensive. For a list of length n, it makes n passes. On each pass, it walks the list from left (index 0) to right, ending at the second-to-last item (index n-2). For each item, it compare the item to its neighbor to the right. So the item at index 0 is compared to the item at index 1. If the one on the left is greater than the one to the right, they are swapped. Then it increments the current index and does the same thing over again until we reach the second to last item. This is one pass. After the first pass, the largest item will have "bubbled" up to the end of the list. We keep making passes until no swaps have been made, which indicates the list is now sorted. In the worst case, we'll have to make n passes. Here's an example using our unsorted array from \ref:

5 | 10 | 3 | 20 | 8 |

5 | 10 | 3 | 20 | 8 |

5 | 3 | 10 | 20 | 8 |

5 | 3 | 10 | 20 | 8 |

5 | 3 | 10 | 8 | 20 |

Here's what the array will look in the second pass:

5 | 3 | 10 | 8 | 20 |

3 | 5 | 10 | 8 | 20 |

3 | 5 | 10 | 8 | 20 |

3 | 5 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

And here's the third pass:

3 | 5 | 10 | 8 | 20 |

3 | 5 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

Even though we were actually done sorting after the second pass, we had to do one more to ensure the list was sorted. The third pass is the first time no swaps were made. We would have needed the additional two passes if our data had been sorted in the exact opposite order (the worst case scenario). Here's a look at what happens after each pass if we start with the list backwards (the green boxes are elements that are in their correct sorted position):

20 | 10 | 8 | 5 | 3 |

10 | 8 | 5 | 3 | 20 |

8 | 5 | 3 | 10 | 20 |

5 | 3 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

Even though it doesn't look like it, we need this last pass to ensure that 3 is
in the correct spot. So, in the worst case, we make n passes, each of which
makes up to n comparisons. Therefore, our complexity is O(n^{2}).

Wikipedia has a nice animated GIF of the process:

## Insertion sort

Insertion sort is another relatively simple algorithm,
and indeed has the same worst case complexity as bubble sort: O(n^{2}).
With insertion sort, we work our way from the left (index 0) to right (index
n-1). The algorithm ensures that everything to the left of the current position
is sorted; everything to the right remains to be sorted. At each step, we take
the item at the current position and insert it to where it belongs in within the
sorted item to the left. In doing this, we need to shift everything from the
sorted side that is greater than the current item to the right one position to
make room for the item. We then move on to the next unsorted item and continue
until we reach the end of the list (all items are to the left).

Wikipedia has a nice animated GIF of the process:

So why is it O(n^{2})? Because the worst case, when the list is in
reverse sorted order, requires that each item be moved to the very left-most
spot, causing n comparisons. Since there are n items, we get a complexity of O(n
× n) = O(n^{2}).

## Selection sort

Yet another simple sorting algorithm is selection
sort, and like the other simple sorting algorithms, has a worst case
complexity of O(n^{2}). Selection sort starts with a pointer at index 0.
It then walks down the list and finds the minimum item. This is then swapped
with the item at the pointer. The pointer is then advanced and we walk from the
pointer to the end of the list searching for the minimum. We keep doing this
until the pointer has reached the last index, at which point, the list is
sorted. Here's the first two passes of our example:

↓ | ||||

5 | 10 | 3 | 20 | 8 |

↓ | ||||

5 | 10 | 3 | 20 | 8 |

↓ | ||||

3 | 10 | 5 | 20 | 8 |

↓ | ||||

3 | 10 | 5 | 20 | 8 |

↓ | ||||

3 | 10 | 5 | 20 | 8 |

↓ | ||||

3 | 5 | 10 | 20 | 8 |

↓ | ||||

3 | 5 | 10 | 20 | 8 |

We wind up with O(n^{2}) because we have to perform n passes, and we
need to perform as many as n comparisons during each pass to find the minimum
item, so n × n comparisons.

## Quick sort

Another sort, called quick sort, is, in the worst
case, as poor a choice as bubble, insertion, and selection sort. However, in the
typical case, quick sort is O(n log_{2} n). Here's how it works. First,
you pick a pivot item. This can be done at random (to
make it easy, just pick the first item). Next, we make two sublists: one with
all the items that are smaller than the pivot item, and another with all the
larger items. This is called the partition step. Now
we do exactly the same process to each of the sublists (it's a multiple
recursion algorithm). Once we end up with sublists of one item, we combine them
in order, forming a sorted sublist. We begin gluing the sorted smaller items
sublist, the pivot, and the sorted sublist of bigger items. We continue to do
this until all sublists have been recombined yielding the full sorted list. Here
are the steps for our array in \ref. The pivot is
the orange box.

5 | 10 | 3 | 20 | 8 |

5 | |||||

3 | 10 | 20 | 8 |

5 | |||||

3 | 10 | 20 | 8 |

5 | ||||

3 | 10 | |||

8 | 20 |

5 | ||||

3 | 10 | |||

8 | 20 |

5 | ||||

3 | 8 | 10 | 20 |

3 | 5 | 8 | 10 | 20 |

So, when is this O(n log_{2} n)? Provided that we pick "good" pivots for
each list/sublist (i.e., ones that will evenly split the list), then we should
wind up with log_{2} n distinct pivots. That's because we need as many
pivots as n can be divided by 2. The n coefficient comes from the fact that each
of the n items in the list needs to, in the limit, be compared to each of the
pivots. So, we get O(n log_{2} n). Now, as we said earlier, this is the
average case, not the worst case. In the worst case, we get O(n^{2}).
Why? Because if we always choose the worst pivot, i.e., the minimum or maximum
for its list/sublist, then we end up with n pivots. That would require a lot of
bad luck, but it can happen. So, the worst case is bad, but in practice, this
algorithm is usually very...quick.

## Merge sort

Merge sort is another recursive algorithm. However,
unlike the previous methods, it runs in O(n log_{2} n) in its average
*and* worst case. That's a pretty solid guarantee. So how's it work? Each
step of the recursion takes an unsorted list. If the list only has one item in
it, it's returned. Otherwise, divide the list in two and sort each half by
making a recursive call. Then, merge the resulting sublists. This requires
keeping track of two pointers; one pointing to the current item in the one
sublist, the other pointing to the current item in the other sublist. The
pointers start by pointing at the first item in their respective sublist.
Take the smaller item of the two being pointed to and append that
to the merged list; advance the corresponding pointer so it points to the next
item in that list. Keep doing this until all items have been taken from both
sublists. Return the merged list. That's it!

Here's an animated GIF courtesy of Wikipedia:

So why is this O(n log_{2} n). The log_{2} n comes from the fact
that we divide the list in half each time. We can divide a list of length n in
half log_{2} n times. For each merge step, we perform at most n
comparisons. Thus, since there are log_{2} n merges, we wind up with a
total of n log_{2} n comparisons.

While merge sort is faster than quick sort, optimized implementations of quick sort are often used in sorting libraries for programming languages. However, merge sort is found in the libraries of many other programming languages. There is one other sort that is also commonly used, which we will not cover, called heap sort. Heap sort is a variation of selection sort, and depends on a data structure called heap.

(Back to top)## Other sorts

There are many other specialized sorts, e.g., made especially for integers or strings. In addition, there are many data structures that sort data automatically upon insertion. For instance, Binary Search Trees and heaps. For the curious, take a look at the Wikipedia page on sorting algorithms.

(Back to top)