Sorting long ListBoxes

General
21

Jim, a shortcoming with your code is that it can only sort doubles arrays with other doubles arrays, whereas SortWith has a capability we lack, the ability to sort any kind of array with any other.

Not a criticism of you, of course, as you really have no other choice within the language.

Even within this narrow use, I wonder if it might not be faster to call SortWith directly where b contains 1 to x arrays, then use your code when Ubound exceeds that arbitrary limit? Something like:

select case b.Ubound
case 0
  dim tmp() as double = b( 0 )
  indexes.SortWith a, tmp
case 1
  dim tmp1() as double = b( 0 )
  dim tmp2() as double = b( 1 )
  indexes.SortWith a, tmp1, tmp2
case 2
…

else
  // Your code
end select
22

Placing this

[code] me.MouseCursor = System.Cursors.Wait
me.SortedColumn = column
me.Sort
me.MouseCursor = System.Cursors.StandardPointer

Return True
[/code]

In the headerpressed event will at least give you the wait cursor while sorting. My testing gives sorting at 1-5 s while loading the table at 8-9s (13 columns 20000 rows).

23

The other alternative is to implement your own sort. I’ve written a BubbleSort in Xojo that worked OK. I got fairly along with a MergeSort as well (definitely more complex to implement than a Bubble) which was quite fast but had some sorting bugs with descending sorts and I set it aside as the BubbleSort was sufficiently fast for the project’s needs.

I implemented this by having a class that represents the rows in the list box, and another class that contains an array of those objects. Then the BubbleSort was like this:

Sub bubble_sort_by_id(sort_direction as integer)

   //bubble sort
  dim swapped as Boolean = True
  dim swap as dealer
  
  while swapped
    swapped = false
    
    for i as integer = 1 to UBound(dealers)
      
      if sort_direction = -1 then //listbox.SortDescending = -1
        if self.dealers(i-1).id < self.dealers(i).id then
          swap = self.dealers(i-1)
          self.dealers.Remove(i-1)
          self.dealers.Insert(i,swap)
          swapped = true
        end if
        
      else //otherwise ascending sort
        if self.dealers(i-1).id > self.dealers(i).id then
          swap = self.dealers(i-1)
          self.dealers.Remove(i-1)
          self.dealers.Insert(i,swap)
          swapped = true
        end if
        
      end if
    next
    
  wend
  

End Sub

In this case, the listbox is represented by a dealers class, with each row represented by a dealer class. At runtime dealers.dealers() is an array of dealer objects. It’s that array of dealer objects being sorted in the sample code above. I based that code off the wikipedia page on Bubble Sort. The example is tied to a very particular use case in my app, but hopefully it conveys the idea.

Charles Yeomans used to have a SortLibrary available for download on his website which had examples how to implement complex sort algorithms in RealBasic. I’m sure someone on the forums has a copy.

There also used to be a sample project called “Sort Algorithms” included with RealStudio, but that seems to have gone away. It had BubbleSort and MergeSort examples but I feel like the Merge implementation was a little off?

24

@Anthony: Why are you using BubbleSort? This is the one algorithm that is always taught to beginners with the reminder not to use because it’s so slow.

25

If your datas are not coming from a database, then why not create a database and store them there instead of filling up the listbox directly.
Afterwards, you can display it in the listbox in any sortmode, you like.

26

That is an excellent notion. Xojo enables you to create an in-memory SQLite database, and that may be a better solution than maintaining an array of objects, doing your own sorts, etc.

27

I use in memory databases quite a bit as holding areas. It allows for great flexibility in displaying info and is quite fast.

28

To overcome the issue here, you could check the arrayType and cast it accordingly… a big cludge, but it could be done.

29

Ok, I put it in a module with a method to cast and sortwith, added methods to accept integer and string as the sorting array… now it should be able to handle the same types as sortWith.

ArraySortTest

30

[quote=98000:@Wayne Golding]Placing this

[code] me.MouseCursor = System.Cursors.Wait
me.SortedColumn = column
me.Sort
me.MouseCursor = System.Cursors.StandardPointer

Return True
[/code]

In the headerpressed event will at least give you the wait cursor while sorting. My testing gives sorting at 1-5 s while loading the table at 8-9s (13 columns 20000 rows).[/quote]

Thanks for your suggestions. This solves one of the problems.

31

Anthony, Beatrix is absolutely correct, BubbleSort is just about the slowest sort of them all. Quite some time ago I decided to write a little program to test 12 different sort algorithms. They are listed below in order of their speed, starting with the slowest. Just for the heck of it I just ran the program, selecting only the last six of the sort algorithms as I did not want to wait for the huge amount of time the slowest six sorts would take. I had it sort a 250,000 element integer array, the same array in the same order for each of the sorts.
Below is the list of sorts with the time in milliseconds for the last 6 of the sorts.

Bubble – not selected
Brute Force – not selected
BiDirectional Bubble – not selected
Exchange – not selected
Shaker – not selected
Insertion – not selected
Merge – 225,469.788
Shell – 1,629.966
Shell/Insertiion – 523.822
Heap – 320.161
Comb – 283.237
Quick – 151.786

Total time for the 6 sorts that ran was 3 minutes, 48 seconds and 378.760 milliseconds and the Merge sort took a huge percentage of that time.

These were run on a 2.25 Ghz dual quad-core Mac Pro

So, there is a big difference in the time for different sorting algorithms. From my experience the bubble sort would have taken at least 5 times longer than the Merge sort, the slowest one I tested with the 250,000 element array. I have found that if you don’t like the idea of recursive sorts, like the Quick sort, the Comb sort is always a close second in speed. I also have a version of the program that shows a graphical representation of the different sort algorithms as they sort bars on a canvas. That needs to be updated to run in Cocoa once I figure out how to clean up the graphics. My method used will not run in Cocoa with its rules on drawing outside of the Paint event.

32

Beatrix - As I mentioned, I implemented bubble sort because it was easy. It happen to be fast enough to meet that particular projects needs so I left it there.

Same reason I shared that example here, because it’s easy to understand the code.

My point was that it’s possible to implement your own sort if needed. I was in no way advocating bubble sort as the “solution” or the best sort option.

Harrie - Perhaps you’d like to share your code? Otherwise, agreed, other sorts are faster, but they’re also meaningfully harder to implement.

It’s easy to say, hey, there’s better ways. Harder to show them. :slight_smile:

33

Another point I notice there is that none of the methods you list as testing, except the merge sort, are stable. For several of the use cases I would typically face, stability is a requirement.

34

(That said, those cases also have small data sets–even 500 entries would be inconceivably huge–so the time required would be much less of a factor.)

35

That’s an excellent point. I’d really like to get back to implementing a merge sort in Xojo. I had ascending working perfectly, but descending had a bug and the related project’s budget simply didn’t cover the time (it worked, sorting wasn’t always quite right with strings)

As I mentioned in my original post, there used to be a Merge Sort example project in RealStudio, but I think it had a bug or two.

99.9% of my projects use a database, so sorting is normally moot for them (the DB handles it) so I’ve never revisited. It seems like something that would be useful to the community (a “drop in" merge soft function - worked with arrays and possibly listbox controls as well)

36

It’s probably only slightly slower to sort your data ascending, then simply reverse the elements.

37

That’s a very good thought Kem, but it bugs me that it didn’t work. Maybe it warrants a weekend project at some point.

It sounds like Harrie might have already worked through a lot of this if he’s open to sharing his code.

38

Yes, and usually I find that if I wanted it in descending order, I can just use some flavor of DownTo when I loop through the array to actually use its contents.

39

I guess since we’re on the subject of sorting, I’ll throw a few sorting functions up here, in case anyone needs them. I make no assurances about bugs, etc., they seem to work fine for me but they haven’t been systematically tested so it’s possible edge cases might break them.

You can change the data type of the toSort() array to double, string, etc., or you change it to a class if there’s some property of the objects that can be compared with > and < and =. You just need to change the data type of the temp variable and, if you’re using objects, change the 1 or 2 places where values are compared to refer to the property you want to compare. There’s probably a more generic way to do it, rather than having to overload & tweak the sorting method for each different class/type, but it’s good enough for me (I tend to not like things that are super-genericized).

First up,
[h]QuickSort:[/h]

[code]Sub QuickSort(toSort() as integer, left as integer = -1, right as integer = -1)
if left = -1 and right = -1 then
left = 0
right = toSort.Ubound
end

dim temp as integer //change data type as needed

dim left2, right2, pivot as integer
left2 = left
right2 = right

if (right - left) > 0 then
pivot = (right + left) / 2
while left2 <= pivot and right2 >= pivot
while toSort(left2) < toSort(pivot) and left2 <= pivot
left2 = left2 + 1
wend
while toSort(right2) > toSort(pivot) and right2 >= pivot
right2 = right2 - 1
wend
'swap values
temp = toSort(left2)
toSort(left2) = toSort(right2)
toSort(right2) = temp

  left2 = left2 + 1
  right2 = right2 - 1
  
  if left2 - 1 = pivot then
    right2 = right2 + 1
    pivot = right2
  Elseif right2 + 1 = pivot then
    left2 = left2 - 1
    pivot = left2
  end
  
Wend
QuickSort(toSort,left,pivot-1)
QuickSort(toSort,pivot+1,right)

end

End Sub
[/code]

40

[h]ShellSort[/h]

[code]Sub Shellsort(toSort() as Integer)
dim h, i, j, ub, temp as Integer
ub = toSort.Ubound

h = 1
while h < ub/3
h = 3 * h + 1
wend

while h >= 1
for i = h to ub
j = i
while j >= h and toSort(j) < toSort(j-h)
'swap
temp = toSort(j)
toSort(j) = toSort(j-h)
toSort(j-h) = temp
'decrement j
j = j-h
wend
next
h = (h-1)/3
wend
End Sub
[/code]