Mintoris Forum

Author Topic: Sorting with Bubblesort  (Read 4336 times)

Jesse

  • Sr. Member
  • ****
  • Posts: 126
  • If life throws a planet at you, pull your ripcord‼
Sorting with Bubblesort
« on: Dec 16, 2010, 08:49 PM »
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

Dave

  • Full Member
  • ***
  • Posts: 39
Re: Sorting with Bubblesort
« Reply #1 on: Dec 17, 2010, 01:17 AM »
Jesse, it's always going to be tough to compare an interpreter speed with native code.  To challenge the built in sort a bit more, I set this up:

Dim a$(999)
Dim b$(999)
For i = 0 to 999
  a$(i) = Str$(Rnd(1))
next I
t = time()
b$ = Sort(a$())
dt = (time()-t)/1000
Print dt

The times varied a bit, but on my HTC Incredible, they mostly ranged between 0.035 to 0.040

Dave

Jesse

  • Sr. Member
  • ****
  • Posts: 126
  • If life throws a planet at you, pull your ripcord‼
Re: Sorting with Bubblesort
« Reply #2 on: Dec 17, 2010, 03:35 PM »
So true‥ So true… On my DX I was getting consistent times of 0.017 so I upped the annie even more by changing the 999's to 9999 and got consistent times of 0.2 seconds. Im afraid to think how long it'd take a bubblesort to arrange 10,000 items :o

Dave

  • Full Member
  • ***
  • Posts: 39
Re: Sorting with Bubblesort
« Reply #3 on: Dec 17, 2010, 04:41 PM »
Jesse, after I posted the 999 results, I did the same thing  I was consistently getting numbers around 0.2 sec also.  It was, however, taking Basic about 9.1 seconds to populate the string array with random numeric strings.

dave

Chuck

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1899
Re: Sorting with Bubblesort
« Reply #4 on: Dec 24, 2010, 12:21 AM »
Jesse, after I posted the 999 results, I did the same thing  I was consistently getting numbers around 0.2 sec also.  It was, however, taking Basic about 9.1 seconds to populate the string array with random numeric strings.

dave

You say it takes 9 sec to populate a 999 element array.  I would be interested to know how long it would take if you used variables that all began with B, J, K, Q, X, Y or Z.

Jesse

  • Sr. Member
  • ****
  • Posts: 126
  • If life throws a planet at you, pull your ripcord‼
Re: Sorting with Bubblesort
« Reply #5 on: Dec 24, 2010, 10:44 PM »
Chuck, remind me via email in the next day or two and id be happy to do it :)

Dave

  • Full Member
  • ***
  • Posts: 39
Re: Sorting with Bubblesort
« Reply #6 on: Dec 26, 2010, 04:19 AM »
Chuck, I ran this code to test the speed improvements that are possible with differing coding styles.  These are listed in decreasing execution times.  I ran each test several times to get an average execution time.

Test #1

dim a$(9999)
t = time()
g = Rnd(-1)
for i = 1 to 10000
  s = Rnd(1)
  a$(i-1) = Str$(s)
next i
print (time()-t)/1000

Time = 10.6 sec

Test #2

dim z$(9999)
t = time()
g = Rnd(-1)
for x = 1 to 10000
  y = Rnd(1)
  z$(x-1) = Str$(y)
next x
print (time()-t)/1000

Time = 8.8 sec

Test #3

dim z$(9999)
t = time()
g = Rnd(-1)
for x = 1 to 10000
  z$(x-1) = Str$(Rnd(1))
next x
print (time()-t)/1000

Time = 8.06

Test #4

dim z$(9999)
t = time()
g = Rnd(-1)
for x = 0 to 9999
  z$(x) = Str$(Rnd(1))
next x
print (time()-t)/1000

Time = 7.65 sec

As you can see from this, for very repetitive programing routines, efficient styles can make a significant difference.

Dave

Chuck

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1899
Re: Sorting with Bubblesort
« Reply #7 on: Dec 26, 2010, 05:59 AM »
Ah, thanks Dave.  Conclusive evidence at last.