Week 11 Programming Exercises - Sorting Arrays

Topics

Compulsory Exercises

These exercises are compulsory and should be done in the labs with your partner. Any you do not finish must be completed in your own time before the next lab. Possible solutions to some are included in the downloadable programs on the DCS100 site.

Exercise 1 - Bubblesort

The 'bubble sort' algorithm repeatedly scans the array from left to right interchanging adjacent elements that are out of order.  The scan is repeated until no out of order pairs are found on a scan. An animation of this algorithm looks like this. This shows graphically how the largest unsorted element 'bubbles up' to the right-hand end.

Write a program that 'bubble sorts' into non-descending order an array of size 20 filled with random integers. Print out the array at the beginning and after every exchange of neighbouring elements. This will enable you to see the bubbling and will also help with debugging.

HINT You will need a swap method to swap adjacent values. Get that working first. Then write a method that does a single pass of an array swapping adjacent values. After it has run the array will not be sorted but the giggest value should at least be in the correct position. Once that is working put it in a loop to do that pass repeatedly until it is sorted.

As an extension to your program, keep a count of both the number of comparisons and swaps of array elements that are made.Print out these counts at the end.

Exercise 2  - Selection sort

Write a program that 'selection sorts' into non-descending order an array of size 20 filled with random integers.  Print out the array after every exchange of elements.

An animation of a slight variant of the simple algorithm that was given in the lectures looks like this. When searching for the minimum unsorted value on each iteration this animated algorithm makes an exchange with any elements smaller than the base.

As an extension to your program, keep a count of both the number of comparisons and swaps of array elements that are made. Print out these counts at the end.
 

Additional Exercises

The following are additional, harder exercises. The more programs you write this week the easier you will find the assessments and the quicker you will learn to program.

Exercise 3  - Binary Search

Write a binary search program (see exercsie from earlier week) that contains a sort method to first sort an array and a search method that does the actual searching of that array.

Exercise 4  - Dictionary ordering

Write a program that reads words (at least 20) from a file and stores them in a String array.  Then sort the array into dictionary order using some sorting algorithm.  Save the words in dictionary order in a new file. To compare values of type String for dictionary ordering you will need to use the String method compareTo, e.g. s.compareTo(t).  This returns the value 0 if the strings are equal, less than 0 if s comes before t in dictionary order and greater than 0 if s comes after t.  You may use Hansen's method readword for reading words from the input dictionary
 

Exercise 5  - Spell checker with an ordered dictionary

Redo the spell checker exercsie from an earlier week with an ordered dictionary file (since the above exercise enables you to generate one). When searching the array representing the dictionary you should now make use of the dictionary ordering by making sure that the search terminates as soon as you know that the word is not present in the dictionary (i.e. when it comes before the word being examined in the dictionary). This will, on average, halve the search time for a word.

There are of course even better search methods for ordered lists. Remember the guessing game from week 5?  The method we indicated could be used by the player in the game was 'binary search'. Here binary search would work as follows. Compare your word against the middle word in the dictionary.  If it comes before that word then repeat the search on the first half of the dictionary, if it comes after the middle word then repeat on the second half.  And so on.... For a dictionary with a million words finding a given word (or finding its absence) will never take more than 20 comparisons using binary search whereas it would on average take half-a-million comparisons using the naive linear search method.