BS Tasks

Now try the following tasks. If you have problems completing them, contact your tutor.

Task 1

Write a program that creates or loads an array of integers. Write a function called bubblesort that sorts a copy of the array of integers and counts how many comparisons and exchanges are required to perform the sort.

Task 2

The Bubble Sort can be made more efficient by being more careful with the count used for the outer loop – it can start at the number of items and be decremented with each pass. (This reflects the fact that we do not need to sort the end items once they are in place.) Write a function called bubblesort2 using this optimisation. Compare its performance with the previous version.

Task 3

Another optimisation that can be used is to put a boolean variable called sorted into the middle loop. If there is a swap during a pass then the dataset is not guaranteed to be sorted, and the value i set to FALSE indicating that another pass needs to be performed. The value is set to TRUE at the beginning of each pass, so if the value of sorted is TRUE at the end of a pass then the data is sorted, and the search can terminate. Implement this optimisation in a function called bubblesort3, and see how much difference it makes. You will probably find that it will make more difference for some data sets than others.

Next: Insertion Sort