Sort Algorithms

Introduction

In the previous lesson, we learned that algorithms which perform a particular task can be studied and compared for efficiency. An algorithm:

• should always generate the correct output
• may vary in the amount of time it takes to execute depending on the input(s)
• may have differing memory requirements
• may have pre-conditions

The two search algorithms we saw (linear search, binary search), both performed the same task (to search for an item in an array) and generated the correct result.

The linear search was much slower on average than the binary search, particularly for large sets of data, however the memory requirements were more or less the same for each, with most of the memory being used by the array itself.

The linear search had no pre-conditions, however binary search had a pre-condition that the array must have been sorted in advance of the search.

These were a nice simple set of algorithms to study and compare. Another set of algorithms we can study and compare are sort algorithms.

Activity 1

Look at the page here which allows you to run a simulation of various sort algorithms.

1. Which two algorithms seem to be slowest with reversed data?
2. Which algorithm is fastest on random data?
3. Which algorithm in your opinion is the best overall?

Bubble sort

Bubble sort is a simple to implement algorithm, where larger values move up the array gradually, like bubbles in a glass containing a fizzy drink.

Essentially, the algorithm moves through the array swapping adjacent pairs of numbers.

• Two adjacent pairs of numbers are compared
• The lower number is swapped into the index position below the higher number.
• If the lower number is already in the correct position nothing needs to happen for that pair.
• The algorithm moves onto the next pair of numbers and repeats the above steps
• Once the array end is reached the whole process (called a pass) repeats
• This keeps happening until it is impossible for any numbers to still need swapping which is a maximum of (n-1)*(n-1) times

Bubble sort algorithm

numbers= [9, 5, 4, 15, 3, 8, 11]
numItems = len (numbers)
for i = 0 to numItems -2
    for j = 0 to (numItems - i - 2)
        if (numbers[j] > numbers[j+1]) then
            temp = numbers [j]
            numbers[j] = numbers[j + 1]
            numbers[j + 1] = temp
        end if
    next j
    print (numbers)
next i

Activity 2

• Implement the bubble sort algorithm in Java.
• Use a method called printArray to print all the elements of the array on a single line.
• Add the number 1 into your array as the last element. Observe how many times it is swapped by looking at the program output.

Activity 3

• Restore the array to its original state by removing the number 1 from the end.
• Modify the program your wrote above so that it uses a flag which is set to true each time a swap happens.
• If no swaps happen in a pass, the program can end early as there is no point continuing.

Insertion sort

The only other sort algorithm needed for OCR AS Computer Science is insertion sort (Merge sort and quick sort are covered in Y13).

In this type of sort, the list is assumed to have two parts, a sorted part on the left and an unsorted part on the right. We keep track of an insertion point in the sorted part of the list, and also keep track of the beginning of the unsorted part of the list.

Steps:

• Element 0 in the array is the sorted part of the array when starting
• Element 1 in the array is the beginning of the unsorted part of the array when starting

Value	9	5	4	15	3	8	11
Index	0	1	2	3	4	5	6

• Inspect element 1 in the array and compare it to element 0. If it is greater than element 0, leave it where it is, otherwise move element 0 to element 1, and element 1 to element 0.

Value	5	9	4	15	3	8	11
Index	0	1	2	3	4	5	6

• The sorted part of the list is now element 0 and 1. Element 2 onwards are unsorted.
• Now inspect every element in the sorted part of the list to find the insertion point (i.e. where element 2 should go)
• Copy every value from the insertion point to the end of the sorted part to its neighbouring position

Value		5	9	15	3	8	11
Index	0	1	2	3	4	5	6

• Copy what was in element 2 into the insertion point

Value	4	5	9	15	3	8	11
Index	0	1	2	3	4	5	6

• Repeat the above for element 3, 4 and so on until the size of the unsorted part is zero

Value	3	4	5	8	9	11	15
Index	0	1	2	3	4	5	6

Algorithm for insertion sort

numbers= [9, 5, 4, 15, 3, 8, 11]
print (numbers)

numItems = len (numbers)
for i = 1 to numItems - 1
    currentVal = numbers[i]
    pos = i
    while pos > 0 and numbers[pos - 1] > currentVal
        numbers[pos] = numbers [pos-1]
        pos = pos -1
    endwhile
    numbers[pos] = currentVal
next

print (numbers)

Activity 4

• Implement the insertion sort algorithm
• Print the array before the sort and after the sort
  • Print the array once each pass and explain to your partner what you see for each pass.

Knowledge check

• Is there a “best” sort algorithm?
• After one pass of the bubble sort algorithm, what is the last item always going to be?
• What two positions do you need to keep track of in an insertion sort?
• List the steps for a bubble sort algorithm
• List the steps for an insertion sort algorithm
• See if you can work out the type of algorithm being used to sort using this activity