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.
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
*It’s really useful to know how this works, not just for Computer Science, but also for maths!
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
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.