Binary Sort

[marnitzg]

Has anyone written a binary sort in VB yet. The one that I wrote seems half the speed of one that I wrote years back in Pascal for dos? Any ideas.

[Jop]

Please provide the Pascal code and we might be able to translate it, my schoolbook about informatics (how do you call it?) has some stuff about Pascal, some sorts too, so I might be able to understand and translate it into VB.

[marnitzg]

Here's the vb code that I have. If you really want the pascal code too then I'll send it as well. I have a class module called llist with the following code:

Public Number As Integer
Public Right As LList, Left As LList


And here is the rest of the code.

'Declarations
Dim Strt As LList
Dim Nth As LList

Private Sub Command1_Click()
List1.Clear
CreateList
ReverseList Strt
Label1.Caption = List1.ListCount
End Sub

'Writes back the sorted list
Private Sub ReverseList(ByVal P As LList)
    If P.Left.Number <> Nth.Number Then Call ReverseList(P.Left)
    List1.AddItem P.Number
    DoEvents
    If P.Right.Number <> Nth.Number Then Call ReverseList(P.Right)
End Sub

'Creates the binary tree
Private Sub CreateList()
Dim Check As Boolean
Dim Counter As Long
Dim Ptr As LList
Dim Nxt As LList
Dim Num As Integer

Set Nth = New LList
Nth.Number = 9999

Set Ptr = New LList
Set Ptr.Right = Nth
Set Ptr.Left = Nth
Randomize
Ptr.Number = Int((900 * Rnd) + 1)
Set Strt = Ptr

For Counter = 1 To 20000
    Randomize
    Num = Int((32000 * Rnd) + 1)
    Set Ptr = Strt
    Check = False
    While Check = False
        Set Nxt = Ptr
        If Ptr.Number < Num Then
         If Ptr.Right.Number <> Nth.Number Then
          Set Ptr = Nxt.Right
         Else: Check = True
        End If
        Else
         If Ptr.Left.Number <> Nth.Number Then
          Set Ptr = Nxt.Left
         Else: Check = True
        End If
        End If
    Wend
        Set Ptr = New LList
        Set Ptr.Right = Nth
        Set Ptr.Left = Nth
        Ptr.Number = Num
        If Nxt.Number < Num Then
         Set Nxt.Right = Ptr
        Else: Set Nxt.Left = Ptr
        End If
Next Counter
End Sub

Simple code and a bit sloppy I know. The part thats a bit slow for me is actually creating the binary tree. Maybe you have a better way of doing it? There is also a way of writing back the tree without using recursive procedures but it gets a bit complicated.

[marnitzg]

Come on. I can't believe that no one has ever needed to sort 30 000 records quickly. Hmmm, I suppose you all take the easy way out and just use the sort of the listbox. Come on people, be adventurous, learn something new. I can assure you that its the fastest way to sort records. So, who wants to learn?

[marnitzg]

Ok. It seems that I will have to venture off and return to visual c. Seems like none of the things that I want done can be done in vb. Damn, vb was such a nice, easy language. Now back to the depths of c hell!

[kedaman]

The sorting methods aren't usually dependent of a certain language, they can be done in any langugage.
There are some threads around here if you search that take up quick, heap and radixsort, i usually use shell sort because it's both fast (n) and nonrecursive. You have to change this to work with your class, since it's written to sort arrays, you could also search on Sort_Shell

Sub Sort_shell(a() As String)
Dim n&, i&, j&, k&, h
 
  n = UBound(a)
  k = n \ 2
  While k > 0
    For i = 0 To n - k
     j = i
     While (j >= 0) And (a(j) > a(j + k))
       h = a(j)
       a(j) = a(j + k)
       a(j + k) = h
       If j > k Then
         j = j - k
       Else
         j = 0
       End If
     Wend
    Next i
    k = k \ 2
   Wend
End Sub

[marnitzg]

Looks similar to a quick sort? Am I wrong, I jsut looked quickly. Anyway, my problem is that I have a minimum of
30 000 records to sort QUICKLY. As in under 30 seconds on a P166. Yes, this is possible with the binary sort (featured above). The thing is, it seems to create the binary tree EXTREMELY slowly which is the problem. I can write a non recursive procedure to write the tree back but I'm keeping it simple as not too many people out there know about binary trees. Anyway, its what all the database programs use to sort their records and I'll gladly explain to anyone who wants to learn.

So, to sum up I need someone to tell me why the tree is being created so slowly. This is normally done extremely fast. (I copied this straight from pascal code I wrote 2 years ago, so I know it has bugs as I couldn't figure out how to set the next pointer value to nul. There fore I made it 9999 which can be chosen as a number (OOPS)

Thanks and if there is anyone who knows anything about binary trees/sorts please reply!

[kedaman]

ACtually i'm just replying to say shell sort isn't recursive, that means of course it's slower...

LList, Is this an object? That might slow down a bit, if you sort an array it will be much faster.

[marnitzg]

An array? How would you be able to use a binary sort with an array? Please show me! Do you know how a binary tree works?

LList is a class module, not an object.

[kedaman]

Classmodule that's what i meant, but that means the objects are LLists.
Look at this thread, Iain posted Quicksort here:
http://forums.vb-world.net/showthrea...threadid=31965
BTW, heap sort should be faster than quick and radix even faster.

[marnitzg]

I have code to do lots of other sorts. The things, I want to get this working. I'm just a person who can't kick a project. Although it does work, its not as fast as it should be. The pascal code I wrote completes this in under 3 seconds. Now. Seeing as class objects are slow, what other mthod can I use. You said something about arrays?

Sorry to keep at it, but its the way I programme and the way I learn!

[kedaman]

Yeah i know noticed Iain used Arrays of UDT's out there, i'm not sure what he put in the UDT but .Name looks like an obvious item, i'm not sure why to use an array of UDT if you have only a name property to it. Of course it may be several data to be sorted parallelly while the .Name determines the sort order. I'm sceptical if there's any other use, why not use a regular array if you for instance only sort values.

VB isn't the best language for this kind of algoritms, arrays have for instance subscript out of range checks that slows down everything (you can check it to compile without them) You could make a Dll in C++ for instance, it would probably run a lot faster. Maybe ASM, but it may be hard to get started.

[marnitzg]

Hence why I said above that I must move back to C.

Whoah. Ok, I just fixed the problem. I ticked favour pentium pro and well, it completes immediately. (Will do, all computers that I use are either pentium pro's or above.)

Anyway thanks for the help. I'll see about making a dll in c. Probably speed it up even more!

[makai]

if you wish to compare timings of sort routines in VB perhaps the following will help:

http://pages.about.com/vbmakai/sortime.htm

[jian2587]

struct TreeNode {
int Data;
struct TreeNode *LeftPtr;
struct TreeNode *RightPtr;
}

Why VB can't use pointer this way?

[marnitzg]

VB doesn't support pointers. You can't self reference a type either. Have no idea why ms left pointers out.

[jian2587]

Eh he he, it doesn't bother me if no pointers...
BUT WHY NO RECURSIVE STRUCTURE!!!???
Damn Microsoft!