Data Warehouse Architect (IL) Next Step Systems US-IL-Chicago Post A Job | Post A Resume

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 values: 7, 3, 5, 6, and 2. 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 [7]
		Now use first 4 elements:
		3 not > 5, no swap
		5 not > 6, no swap
		6 > 2, so swap: 3 5 2 6 [7]
	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 (N-1). The second pass through will have (N-2) comparisons, then (N-3) 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) * NLog(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
N	Bubble Sort	QuickSort
10	45 (45 what? - I dunno 45 thinking cycles)	83
15	105	147
20	190	216
25	300	290 (QuickSort wins)
50	1,225	705
1000	500,000 (Bubble Sort is 20 times slower!)	25,000

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):

Sub SingleSorter( byRef arrArray ) Dim row, j Dim StartingKeyValue, NewKeyValue, swap_pos For row = 0 To UBound( arrArray ) - 1 'Take a snapshot of the first element 'in the array because if there is a 'smaller value elsewhere in the array 'we'll need to do a swap. StartingKeyValue = arrArray ( row ) NewKeyValue = arrArray ( row ) swap_pos = row For j = row + 1 to UBound( arrArray ) 'Start inner loop. If arrArray ( j ) < NewKeyValue Then 'This is now the lowest number - 'remember it's position. swap_pos = j NewKeyValue = arrArray ( j ) End If Next If swap_pos <> row Then 'If we get here then we are about to do a swap 'within the array. arrArray ( swap_pos ) = StartingKeyValue arrArray ( row ) = NewKeyValue End If Next End Sub

[View 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!