Sorting Algorithms | TeachAllAboutIT

Sorting algorithms in computer science range from very simple, to very complex and there are two main sorting algorithms taught at GCSE. Sorting is the term applied to taking the items in an array and arranging them in either ascending (alpha / numerical order) or descending (reverse) order. It’s useful at this stage to make sure that you know what the terms data set, array, and items are.

Bubble Sort

The first of these sorting algorithms to be discovered was Bubble Sort*.

In this, items are looks at in pairs and swapped in a ‘pass’ of the array which then repeats until no swaps have been made in a full pass. The algorithm for this looks like:

Swaps <-- 1

WHILE Swaps >0 DO

  Swaps <-- 0

  FOR i <-- 0 TO LENGTH(myList)-1 DO

     IF myList[i] > myList[i+1] THEN

           Swaps <-- Swaps +1

           Temp <-- MyList[i]

           MyList[i] <-- MyList[i+1]

           MyList[i+1] <-- Temp

      END IF

   END FOR

*It’s really useful to know how this works, not just for Computer Science, but also for maths!

Insertion Sort

The second of these sorting algorithms is Insertion Sort. This sorting algorithm is likely to be one that you have seen a number of times before, but haven’t thought about the steps that you have used to implement it.

Imagine that you have a stack of exam papers that you need to put in order of Surname:

You hold the unsorted stack (the unsorted portion
and put a single paper down (the sorted portion)
You take the next paper and compare it to the sorted paper
and place (insert) it into the correct place in the sorted pile
You continue doing this until no more papers are left unsorted

Exactly the same happens in Insertion Sort, except we need to add in some logic of how to compare each item from highest to lowest in the sorted portion of the list and move them up one at a time to make room.

You’ll notice that in each of the algorithms, there is additional logic for moving items around in the array – if you simply moved the item up one you would overwrite another item. Understanding that we use temporary variables to move items around in a list is a large part of the Arrays section in the Programming topic.

Merge Sort

Merge sort is a more efficient recursive algorithm that uses the same idea of Divide & Conquer that we saw in Binary Search.

In merge sort, a list of items is divided down into smaller & smaller arrays until each item is in a separate array. The logic behind this is that an item 1 in length cannot possibly be unsorted!

Once it is divided down, the arrays are merged back together in pairs by comparing the leftmost item in each (that hasn’t already been merged), then adding the lowest to the new merge list.

This process is repeated until a single sorted list has been reconstructed.