Sorting a One-Dimensional Array using a Bubble SortBy Darren Neimke
|Sorting Two-Dimensional Arrays|
|In this article we examine how to sort one-dimensional arrays using Bubble Sort. There is another article of mine that looks at sorting two-dimensional arrays using Bubble Sort as well as sorting arrays of objects! Once you have read this article, be sure to check out: Sorting a Two-Dimensional Array using a Bubble Sort!|
I can say that I definintely learned something really cool in this last week. I was given the assignment of reading our IIS log files and constructing management reports from the data. It didn't take me long to realize that working with data without the benefit of SQL is long winded.
Each file was the equivalent of one day's statistics so I decided that I'd
place all of the data for each file into its own
Day object. So I created
a Class accordingly. This enabled me to have many properties for each
day, such as the Date, Number of Hits, Number of Visitors, Bytes Sent and
Bytes Received. After a considerable amount of data munging I ended up with a Dictionary
object full of
Day Objects with the dates as the Keys.
(For more information on creating classes with VBScript be sure to read:
Using Classes within VBScript!)
Now came the tough part. I had to work out how to sort my data. For example some people would like their reports shown in Date ascending order and some would like it shown in Hits ascending order. I'd never sorted an array before, never mind a Dictionary full of Objects.
Let's start at the beginning. What are we trying to achieve here? How could we go about
sorting a list of data? Imagine, for a moment, that we had an array with the following
One way that we could sort this would be to start from the left, placing the leftmost digit
in its proper place... and once that was moved, we could return to the leftmost digit and place
it in the right spot and so on... If the leftmost digit belonged in the leftmost spot, we could
then start the process all over again for the second digit from the left.
This explanation may be a bit confusing, so let's look at an example of how these digits would get shifted around to their correct spots.
Starting: 7 3 5 6 2 Use all 5 elements: 7 > 3, so swap: 3 7 5 6 2 7 > 5, so swap: 3 5 7 6 2 7 > 6, so swap: 3 5 6 7 2 7 > 2, so swap: 3 5 6 2 7 3 5 6 2  Now use first 4 elements: 3 not > 5, no swap 5 not > 6, no swap 6 > 2, so swap: 3 5 2 6  3 5 2 [6 7] 3 elements: 3 not > 5, no swap 5 > 2, so swap: 3 2 5 [6 7] 3 2 [5 6 7] 2 elements: 3 > 2, so swap: 2 3 [5 6 7] 2 [3 5 6 7] 1 element: nothing to do [2 3 5 6 7]
This method is called a Bubble Sort. The keyword 'bubble' in bubble sort indicates that elements are bubbling to the top of the array..
With a brief analysis of this method it is fairly evident that
the number of comparisons in the first pass is
second pass through will have
(N-2) comparisons, then
and so on until there is 1 comparison. i.e.
(N-1) + (N-2) + (N-3)
+ (N-4) ... + 1 or
((N^2 - N) / 2) - trust me. :-)
This contrasts with the QuickSort method. Without going into
the details of how it works my year 12 math suggests to me that
the number of comparisons required is
((N / 2) * N Log(2)).
(For more information on sorting arrays using the QuickSort algorithm, be sure
to read: Sorting Arrays with VBScript using QuickSort!)
Now, comparisons in the QuickSort method involve comparing three values together (and swapping their positions where appropriate) where our Bubble Sort only operates on two values at a time. Let us assume that a QuickSort comparison (and value swap) takes on average five times longer than the corresponding operation within the Bubble Sort. This is a guess, but I reckon it would be closer to five than 50.
Therefore to find the size of an array at which the QuickSort
becomes more efficient than a Bubble Sort (the Bubble Sort is more efficient for
small sorts), we need to find the smallest N where
(N^2 - N) / 2) > (5 * (N / 2)
Although we probably covered this stuff in year 12 and I'm sure that a decent Mathematician could work it out (and that's only assuming he doesn't know it off the top of his head), I'm not going to even bother trying as it is irrelevant (especially because I plucked the 5 out of thin air). Of more use to this discussion is to compare the different results for a few different values of N (yes - trial & error).
|Bubble Sort vs. QuickSort Performance|
(45 what? - I dunno 45 thinking cycles)
(Bubble Sort is 20 times slower!)
This demonstrates that when dealing with large (or even not small arrays) the Bubble Sort becomes a lot less efficient than the QuickSort as the number of elements increases.
Let's (finally) look at the code in our Bubble Sort to sort a 1 dimensional array (you can also check out the live demo):
That wraps up this article! Be sure to also read my article on sorting two-dimensional arrays with Bubble Sort and sorting arrays of objects: Sorting a Two-Dimensional Array using a Bubble Sort! Happy Programming!