FriedSpace.com

Space for Cooking up Great Ideas

Space for Cooking up Great Ideas

FriedSpace

Module 3

Other Modules

Announcements

In many cases, it is quite convenient to store all the data that will be sorted by a bubble sort algorithm in a linked list. The bubble sort then rearranges the nodes in the linked list until they are all in the correct order. However, in our case, we will implement a version of the bubble sort algorithm in which the information to be sorted is held in an array.

The first step will be to define a data structure which holds the information from a single line of the weblog. This structure will have fields corresponding to the IP address and HTTP code, and various other fields for the remaining data.

Let us suppose we call such a structure a `logType`. There are two ways we can proceed from this point: either we can set up an array whose entries are of type `logType`, or we can set up an array, each of whose entries is a *pointer* to a `logType`.

The latter is more convenient, since changing the order of an array of pointers is quite simple, whereas rearranging an array of entries of type `logType` would require us to be physically moving all the blocks of type `logType` around in memory. Moving the pointers alone allows-na us to keep the actual data itself right where it is. This is of course not only easier to implement, but more efficient too.

A bubble sort algorithm is very simple. It simply proceeds through the array in order, entry by entry, and compares each entry with the entry that follows-na. There are two possibilities: either the two entries are supposed to be in that order with repsect to each other in the final sorted array, or they are currently in the wrong order with respect to each other. If the two are not ordered correctly, the bubble sort simply swaps them and continues on. Once the bubble sort reaches the end of the array, it then returns to the beginning and repeats the same procedure through the entire array, over and over again. It magically turns out that if there are `n` entries in the array, the bubble sort just needs to proceed through the entire array a total of `n-1` times using this "check and swap algorithm", and then the array will be entirely sorted.