### Sorting Algorithms

Click to see the rest of the Algorithms section :

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

END IF

END FOR

*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

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.