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.
Printable View
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.
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.
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.
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.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
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?
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!
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
Code: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
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!
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.
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.
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.
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!
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.
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!
if you wish to compare timings of sort routines in VB perhaps the following will help:
http://pages.about.com/vbmakai/sortime.htm
struct TreeNode {
int Data;
struct TreeNode *LeftPtr;
struct TreeNode *RightPtr;
}
Why VB can't use pointer this way?
VB doesn't support pointers. You can't self reference a type either. Have no idea why ms left pointers out.
Eh he he, it doesn't bother me if no pointers...
BUT WHY NO RECURSIVE STRUCTURE!!!???
Damn Microsoft!