So I'm working on the initial thought process on a checkbook program for my wife and I realize I need to quickly sort a list of up to maybe 100 payee names. I'm thinking a bubblesort will work fine, but I research sorting algorithms anyway. Mintoris Basic isn't currently suited for Quicksort, my favorite. So I'm reading about Heapsort and how it will compare many elements but only re-order those necessary. I wondered if that thought could be applied to Bubblesort. Here's what I found:
First let's set everything up. Dimension our arrays, one to sort and one to hold the same unsorted order, seed the random number generator, fill the array with random numbers 0 - 99.99999, with whole and fractional parts, display the array for our viewing pleasure, and make a backup array so we can test both versions of the algorithm on the exact same array of values.
setup:
dim a$(99)
dim b$(0)
i = rnd(-1)
for i = 0 to 99
a$(i) = str$(rnd(100) + rnd(1))
next i
list a$(), a
b$() = a$()
Ok. Now for the Bubblesort. This is a standard Bubblesort with no modifications, except to keep track of, and display, expired time and show the sorted list. Bubblesorts work by comparing two items. The compared items bubble up from the bottom, or start, of the lust towards the top, or end. There are two loops, an outer loop, indexed in the example by the For loop variable i, and an inner which is indexed by j. The outer starts at the bottom of the list and increments towards the top and stops at the next to the top item. The inner loop executes fully for each increment of the outer loop, and starts at the top of the outer loop plus one, and increments to the top of the list. At each inner loop increment, the item at the outer and inner loop index positions are compared. If the inner loop item is less than the outer loop position, their values are swapped with each other. This continues until the outer loop has finished incrementing to the next to the topmost item.
bubblesort:
t = time()
for i = 0 to 98
for j = i + 1 to 99
if a$(j) < a$(i) then
a$ = a$(i)
a$(i) = a$(j)
a$(j) = a$
endif
next j
next i
t = (time() - t) / 1000
dialog "Bubblesort", str$(t) + " seconds"
popup "Touch any item in the list to continue"
list a$(), a
Now here's the problem: it takes about 3.5 seconds for the sort itself to execute on my handy dandy Droid X. That's about 3 seconds too long. So is there a way to improve the speed? Let's see. We can't reduce the number of comparisons in a Bubblesort without changing the structure into a different kind ir sort. Drat‼ So what's left? What about all those string variable swaps? Its entirely possible, and plausible, for several swaps to take place during each outer loop increment / inner loop execution. But wait. What's the purpose of the inner loop execution? To bring the smallest item in its span to the current index position of the outer loop. So why does it spend time unnecessarily swapping variables over and over again, when it only needs to swap once per inner loop execution? Good question. How about we set a comparison string variable, c$, and an index position pointer, a, before the inner loop starts to execute? Then, each increment, or iteration actually, compares the currect inner loop index position value to the comparison string, c$, and if its smaller, just make c$ equal to the now lower value and remember the inner loop index in variable a. At the end of the inner loop execution, we check to see if our index variable has changed, and if it has, we perform a much simpler swap, because we already have the lowest value in c$. The rest of the algorithm is the same. This modification drops the execution time from 3.5 to 1.6 seconds. Wow. So it does take a little time for all that swapping around.
modifiedbubblesort:
a$() = b$()
t = time()
for i = 0 to 98
c$ = a$(i)
a = -1
for j = i + 1 to 99
if a$(j) < c$ then
c$ = a$(j)
a = j
endif
next j
if a > -1 then
a$(a) = a$(i)
a$(i) = c$
endif
next i
t = (time() - t) / 1000
dialog "Modified Bsort", str$(t) + " seconds"
popup "Touch any item in the list to continue"
list a$(), a
It should be noted that this modified Bubblesort ligic has most likely been thought of before, so i take no credit for its originality. I only take credit that I was able to think of it on my own with only a spark of an idea from another reference.
Well I was quite proud of myself for losing over half the execution time. I was going to write a new suggestion for a basic Sort command when it dawned on me that i'd better check first, so i did and found Chuck had already put one in place. Talk about a Duh‼ moment. Well, I had to compare the results of my previous tests with the execution time of the built-in Sort statement.
sortstatement:
t = time()
a$() = sort(b$())
t = (time() - t) / 1000
dialog "Sort() statement", str$(t) + " seconds"
popup "Touch any item in the list to continue"
list a$(), a
Im happy to report the built in Sort statement sorted the array in an average of 0.015 seconds. I think I'll use the built in one.
If you want, you can put the pieces of code together and run the test yourself. Sorry I can't upload the basic file at the moment. Happy sorting‼
Jesse
Topic: Sorting with Bubblesort (Read 4336 times)
Mintoris Forum