Digital design principles - CCEASorting algorithms

A sorting algorithm is designed to sort a set of data into order (either increasing or decreasing). For example, a list of customer names could be sorted into alphabetical order by surname, or a list of people could be put into descending numerical order by age.

Bubble sort

A bubble sort starts at the beginning of an array and checks the first item against the second item. If the first item is greater than the second item, the algorithm swaps them. If the first item is less than the second item, it then moves onto the second item and checks this against the third item in the array. If it is greater than the third item, it swaps them; otherwise it performs no swap and moves on.

This process is repeated until the end of the array. If there are 100 values to sort, each pass through the list will take 99 comparisons – and you might have to repeat it 99 times.

After the first pass, the algorithm will start again at the beginning of the array and repeat the same process. It will repeatedly pass through the data until it makes no changes. It then knows the data is in order.

The bubble sort gets it name from the way the largest numbers 'bubble' up to the end of each pass.

The bubble sort can be represented with the following algorithm:

array = [4, 2, 23, 31, 16, 3] # Array to be sorted
length = array.length – 1 # Subtract 1 from length as count will begin at 0
swapped = true # a flag variable used exit the while loop
WHILE swapped == true swapCount = 0 # counter variable for the sort for n = 0 to length # Loop through each element in the array IF array[n] > array[n+1] then # compare the elements list[n] == list[n+1] # if it is larger swap swapCount = swapCount + 1 #count the number of swaps ENDIF next n IFswapCount == 0 # if no swaps occur on a pass the sort will end swapped = false ENDIF
ENDWHILE

Insertion sort

An insertion sort is an efficient algorithm for sorting a small number of elements. Insertion sort works the same way as sorting a hand of playing cards, i.e. starting with an empty left hand and the cards face down on the table. One card at a time is then removed from the table and inserted into the correct position in the left hand. To find the correct position for a card, it is compared with each of the cards already in the hand, from right to left.

The insertion sort can be represented with the following algorithm:

FOR counter = 1 TO LEN(list) temp = list[counter] # place the first element in the list into a temporary variable counter2 = counter # second counter variable for while loop WHILE counter2 >0 AND list[counter2-1] > temp # compare value to the value on the left list[counter2] = list[counter2-1] # swap the values counter2 = counter2 – 1 # decrease counter2 END WHILE list[counter2] = temp
NEXT counter