Simple sorting algorithms

If, like me, you studied some computer science at university, you were once intimately familiar with a number of sorting algorithms. But now the exact details are a bit fuzzy, and all that remains of that knowledge is a voice in the back of your mind saying “Whatever you do, don’t use bubble sort.” Here’s a short refresher of two of the simpler sorting algorithms. These are the easiest to grasp conceptually, but the most computationally inefficient.

Insertion Sort

Insertion sort is best illustrated on a partially sorted list. For example, this list has the first four elements sorted:

0 2 5 6 3 7 5 1

Now we wish to sort the fifth element, 3. Moving backwards from 3, we find that it should be between the 2 and 5:

0 2 5 6 3 7 5 1

5 and 6 are shifted up to make way for 3, and the list is now sorted up to and including the fifth element:

0 2 3 5 6 7 5 1

When sorting the sixth element, 7, we find that it’s already in place so there’s no need to do anything. Then, the 5 is moved to the correct place, followed by the 1 to give a fully sorted list:

0 1 2 3 5 5 6 7

Insertion sort can be done in-place, so memory requirements are O(1). In the best case, when the list is already sorted, there is no need to do any swaps and only one comparison per element in the list, so the running time is O(n). However, average and worst case running times are O(n2).

Selection sort

Selection sort starts by finding the smallest element in the list and placing it at the beginning. Then placing the second smallest in second place and so on, till the list is sorted. For example, the list to be sorted is:

4 8 2 3 9 5

The first step is to look through the whole list to find the smallest element is 2. This is swapped with the 4 at the beginning of the list:

2 8 4 3 9 5

Now 2 is in the right place, so we look through the rest of the list to find the next smallest element, and so swap 3 and 8:

2 3 4 8 9 5

Next, we look through the rest of the unsorted list to discover that 4 is in the right place so there’s no need to swap:

2 3 4 8 9 5

Finally, swapping 5 and 8, then 8 and 9 gives a fully sorted list:

2 3 4 5 8 9

This can be done in-place so the extra memory needed is O(1), but the computational complexity is O(n2) in the best, worst and averages cases, as you always need to go through the whole list n times.

Advertisements
This entry was posted in Technology and tagged , , , , , . Bookmark the permalink.

One Response to Simple sorting algorithms

  1. Pingback: Divide-and-conquer sorting algorithms | My computer doesn't listen

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s