Sorts
KT
have sort routines built into them, but I cant find one in VB. I need to
sort MULTIPLE fields. For Example, an array of strings containing:
000001 12/02/2001 Doe,John 12218 nowhere rd. CA. 90210
000002 12/16/2000 Doe,Jane 12210 nowhere rd. CA. 90210
how could I sort these strings based on date, lastname and firstname??
I cant seem to find a sort routine that will do multiple keys. I tried
mod'ing a quicksort routine and calling it 3 times comparing the substrings
like date, then
lastname, then firstname using MID functions but that re arranges them on
each call. There's got to be an easy way to do this, I know you can
highlight the column(s) in MS ACCESS and hit sort asc/desc and it will sort
all the columns at one time. I'm not using a DB, using arrays.
Thanks KT
kta...@trentech.com
Jon Oliver
news:OHye63hmBHA.2480@tkmsftngp04...
> Please Help, I can't seem to find a way to sort an array in
VB. Most lang's
> have sort routines built into them, but I cant find one in VB.
Just curious, what languages are you thinking of?
> I need to
> sort MULTIPLE fields. For Example, an array of strings
containing:
> 000001 12/02/2001 Doe,John 12218 nowhere rd. CA. 90210
> 000002 12/16/2000 Doe,Jane 12210 nowhere rd. CA. 90210
>
> how could I sort these strings based on date, lastname and
firstname??
>
> I cant seem to find a sort routine that will do multiple keys.
I tried
> mod'ing a quicksort routine and calling it 3 times comparing
the substrings
> like date, then
> lastname, then firstname using MID functions but that re
arranges them on
> each call.
The trick with multiple keys is that there's a nested (not
serial) relationship to the keys.
For a single-key sort, there's some logic in the middle of your
loop that determines if PrimaryValue1 is less than, greater than
or equal to PrimaryValue2. (For convenience, let's refer to
those results as -1, 1 and 0 respectively.) The comparison
might look something like this:
If PrimaryValue1 < PrimaryValue2 Then
Compare = -1
Else If PrimaryValue1 > PrimaryValue2 Then
Compare = 1
Else
Compare = 0
End If
For multiple keys, just nest the conditions to handle secondary,
tertiary, etc keys
If PrimaryValue1 < PrimaryValue2 Then
Compare = -1
Else If PrimaryValue1 > PrimaryValue2 Then
Compare = 1
Else
If SecondaryValue1 < SecondaryValue2 Then
Compare = -1
Else If SecondaryValue1 > SecondaryValue2 Then
Compare = 1
Else
If TertiaryValue1 < TertiaryValue2 Then
Compare = -1
Else If TertiaryValue1 > TertiaryValue2 Then
Compare = 1
Else
Compare = 0
End If
End If
End If
KT
Thanks KT
"Jon Oliver" <jol...@no.spam.maam.com> wrote in message
news:uH2x5CimBHA.708@tkmsftngp03...
Jon Oliver
> C (standard lib)
> JAVA
A library rates as a language feature?
> Powerbuilder
This one I can buy, because of it's DB origins.
Joe "Nuke Me Xemu" Foster
> Please Help, I can't seem to find a way to sort an array in VB. Most lang's
> have sort routines built into them, but I cant find one in VB. I need to
> sort MULTIPLE fields. For Example, an array of strings containing:
> 000001 12/02/2001 Doe,John 12218 nowhere rd. CA. 90210
> 000002 12/16/2000 Doe,Jane 12210 nowhere rd. CA. 90210
>
> how could I sort these strings based on date, lastname and firstname??
Are you free to rearrange the strings a bit? If you can reformat
them as something more like this, you can use plain old Quicksort:
2001-12-02 Doe,John 12218 nowhere rd. CA. 90210 000001
2000-12-26 Doe,Jane 12210 nowhere rd. CA. 90210 000002
I'd want to find some other character to separate the fields, to
make it easier later to put things back the way you found them.
--
Joe Foster <mailto:jlfoster%40znet.com> Sign the Check! <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above They're coming to
because my cats have apparently learned to type. take me away, ha ha!
Tracy Thomason
With a value of 9 it comes in below parens and a few other symbol
characters.
"Joe "Nuke Me Xemu" Foster" <j...@bftsi0.UUCP> wrote in message
news:OYOP4fimBHA.2116@tkmsftngp03...
Larry Serflaten
"Joe "Nuke Me Xemu" Foster" <j...@bftsi0.UUCP> wrote
>
> Are you free to rearrange the strings a bit? If you can reformat
> them as something more like this, you can use plain old Quicksort:
>
> 2001-12-02 Doe,John 12218 nowhere rd. CA. 90210 000001
> 2000-12-26 Doe,Jane 12210 nowhere rd. CA. 90210 000002
A couple years ago, I did something similar using a recursive
Merge sort on a _large_ set of data. It worked like a charm!
:-)
LFS
Matthew Curland
http://www.fawcette.com/archives/magazines/vsm/ for reusable easily reusable
qsort routines.
You might be better off here to pre-parse the strings into an array of
structures first so that you don't have to constantly reparse them. The
extra memory you use is likely to be less than the extra string memory you
alloc/free by reparsing the same item multiple times during the sort.
To get an accurate sort, you need to do all of the work in a single Compare
function, as pointed out in other responses.
The first article shows the basic function pointer sorting approach, the
second makes it very easy to sort an indexing array instead of the data
itself. -Matt
"KT" <kta...@trentech.com> wrote in message
news:OHye63hmBHA.2480@tkmsftngp04...
KT
mostly lib or DLL calls and other OCX issues, speaking from a windows / API
standpoint. DLL here, DLL there, DLL everywhere.. Windows kindof forces you
to use those things, even in assembly sometimes..
"Jon Oliver" <jol...@no.spam.maam.com> wrote in message
news:uzfPAbimBHA.2104@tkmsftngp07...
Willy Van den Driessche
http://users.skynet.be/wvdd2/Sorting/sorting.html
--
Van den Driessche Willy
For a work in progress :
http://users.skynet.be/wvdd2/index.html
stu
stu
"Larry Serflaten" <serf...@usinternet.com> wrote in message
news:urbkjBjmBHA.2024@tkmsftngp03...
Larry Serflaten
"stu" <smcg...@yahoo.com_> wrote
> > A couple years ago, I did something similar using a recursive
> > Merge sort on a _large_ set of data. It worked like a charm!
> would you not run out of stack space on a large sort?
Evidently not. If I remember correctly, the sort is done in a
binary tree fashion such that on the first pass the list is divided
in to two parts, one of which is passed back recursively, ahead
of the other. That continues down one side of the tree to the
end (I think I stopped at 16 elements in a list to do the Selection
sort) where it starts returning back up the tree doing the other list
in the branch.
Thats works just like a binary number, when you add another bit, you
get twice as many values. Here, you can figure that for each call I
had to make, the list was twice as large. Assuming it took 64 calls
to divide the list down to one element, then the list contained
2^63 elements. 63 calls on the stack is not many at all, but that
would mean the list contained 9223372036854775808 elements.
I am sure I did not even go that far...
<g>
LFS
Billy Joe
http://home.adelphia.net/~bjb1939/
04. Demonstration: QSort Colored Lines. A demo of QSort vs. Shell Sort vs.
Counting Sort. Also monitors stack depth and illustrates using pre-check for
pre-sorted lists.
If you do, be sure to try an inverted QSort to see what happens!
--
Regards,
Billy Joe
"stu" <smcg...@yahoo.com_> wrote in message
news:DtY%7.2328$WQ1.4...@news6-win.server.ntlworld.com...
Joe "Nuke Me Xemu" Foster
> For some inspiration you could look at :
> http://users.skynet.be/wvdd2/Sorting/sorting.html
Because your sorting components use comparisons between keys, they impose
the use of O(n * log n) sorting algorithms, correct? The "debunkings" of
O(n) sorting algorithms, such as radix sorting and "binsort", that I've
seen all presuppose that O(n) additional storage is required, a severe
drawback. However, some exercises in Chapter 9 of Cormen, Leiserson, and
Rivest's _Introduction to Algorithms_ imply that an O(n) sort requiring
only constant additional space is within the reach of a computer science
undergraduate. Perhaps Microshaft is reserving O(n) in-place sorting for
their own .NET applications? I also wonder why you sort your "words.txt"
using a Variant, of all things, to hold the word list. Was this overhead
demanded by Microshaft so that VB.NyET's Array.Sort would look better, a
necessary condition before they would grant permission for you to reveal
benchmark results, according to the terms of the .NET Beta 2 SDK EULA?
--
Joe Foster <mailto:jlfoster%40znet.com> "Regged" again? <http://www.xenu.net/>
Willy Van den Driessche
> the use of O(n * log n) sorting algorithms, correct? The "debunkings" of
> O(n) sorting algorithms, such as radix sorting and "binsort", that I've
> seen all presuppose that O(n) additional storage is required, a severe
> drawback. However, some exercises in Chapter 9 of Cormen, Leiserson, and
> Rivest's _Introduction to Algorithms_ imply that an O(n) sort requiring
> only constant additional space is within the reach of a computer science
> undergraduate. Perhaps Microshaft is reserving O(n) in-place sorting for
> their own .NET applications?
correct me if I'm wrong, both of these pose additional requirements on the
data in the container. I think it's impossible to fit them under the
comparer/sortableContainer/SortAlgorithm umbrella. I'd be interested to be
proven wrong.
My sorting component is of course just a component. It serves its purpose
but I don't pretend that it solves all sorting problems. For those cases
where it matches and you don't need screaming performance I think it does
it's job quite well. P.e : it only takes 10-20% more to sort a listbox than
the native "sorted" method does. But it does let you sort that listbox in
any way you like (unlike the sorted property).
> I also wonder why you sort your "words.txt"
> using a Variant, of all things, to hold the word list.
Actually, It was a quick code. It has more to do with the Split function
returning a Variant than anything else. I was not even aware of the
problem. I changed the benchmarking project to use an array of strings
instead for varwords. Pretty much as I expected, the results don't change.
I'll post the corrected zipFile this week. That doesn't mean you are not
correct of course. Using a variant is not the ideal choice - to say the
least. Thank for pointing me to that oversight.
>Was this overhead
> demanded by Microshaft so that VB.NyET's Array.Sort would look better, a
> necessary condition before they would grant permission for you to reveal
> benchmark results, according to the terms of the .NET Beta 2 SDK EULA?
I was not even aware that I needed permission to write the benchmark in
.NET. If that's the case, I will be glad to remove it from my site until
.NET is released. I don't expect a spectacular performance change in the
released version. It's hard to argue that array.Sort is not an advancement.
VB6 should have had it's own Sort method built-in too. As array.Sort is a
general purpose implementation -like my component- it shouldn't prove too
hard to beat it on performance. It's hard to beat on ease of use though.
--
Van den Driessche Willy
For a work in progress :
http://users.skynet.be/wvdd2/index.html
"Joe "Nuke Me Xemu" Foster" <j...@bftsi0.UUCP> wrote in message
news:e#8kVJUnBHA.1780@tkmsftngp05...
> "Willy Van den Driessche" <Willy.Van.d...@skynet.be> wrote in
message <news:OSSwg4umBHA.2156@tkmsftngp07>...
>
> > For some inspiration you could look at :
> > http://users.skynet.be/wvdd2/Sorting/sorting.html
>
>
Joe "Nuke Me Xemu" Foster
> > Because your sorting components use comparisons between keys, they impose
> > the use of O(n * log n) sorting algorithms, correct? The "debunkings" of
> > O(n) sorting algorithms, such as radix sorting and "binsort", that I've
> > seen all presuppose that O(n) additional storage is required, a severe
> > drawback. However, some exercises in Chapter 9 of Cormen, Leiserson, and
> > Rivest's _Introduction to Algorithms_ imply that an O(n) sort requiring
> > only constant additional space is within the reach of a computer science
> > undergraduate. Perhaps Microshaft is reserving O(n) in-place sorting for
> > their own .NET applications?
> I have been pointed to the lack of radix- and binsort before. However,
> correct me if I'm wrong, both of these pose additional requirements on the
> data in the container. I think it's impossible to fit them under the
> comparer/sortableContainer/SortAlgorithm umbrella. I'd be interested to be
> proven wrong.
You're right about the inability of your containers to incorporate O(n)
sorting algorithms.
> My sorting component is of course just a component. It serves its purpose
> but I don't pretend that it solves all sorting problems. For those cases
> where it matches and you don't need screaming performance I think it does
> it's job quite well. P.e : it only takes 10-20% more to sort a listbox than
> the native "sorted" method does. But it does let you sort that listbox in
> any way you like (unlike the sorted property).
Displayed items in a listbox must all be strings anyway, so I don't see
how limiting the keys to being strings compromises flexibility. Indeed,
it should not be difficult to serialize any key that can be represented
in a digital computer in such a way that an in-place O(n) sort can work
with it. Dates and times could be represented using the ISO yyyy-mm-dd
and hh:nn:ss formats, while floating-point numbers could be represented
with the sign first, then the exponent, and finally the mantissa.
> > I also wonder why you sort your "words.txt"
> > using a Variant, of all things, to hold the word list.
>
> Actually, It was a quick code. It has more to do with the Split function
> returning a Variant than anything else. I was not even aware of the
> problem. I changed the benchmarking project to use an array of strings
> instead for varwords. Pretty much as I expected, the results don't change.
> I'll post the corrected zipFile this week. That doesn't mean you are not
> correct of course. Using a variant is not the ideal choice - to say the
> least. Thank for pointing me to that oversight.
Using an array of plain old strings also allows you to leverage some of
the "advanced optimizations" as well as opens the door to a potentially
much faster way to swap strings. This has yet to fail me:
Declare Sub RtlMoveMemory Lib "Kernel32" (ByRef Dest As Any, ByRef Source As Any, ByVal Length As Long)
Sub StrSwap(ByRef Str1 As String, ByRef Str2 As String)
Dim Temp As Long: Temp = StrPtr(Str1)
RtlMoveMemory ByVal VarPtr(Str1), ByVal VarPtr(Str2), 4
RtlMoveMemory ByVal VarPtr(Str2), ByVal VarPtr(Temp), 4
End Sub
> >Was this overhead
> > demanded by Microshaft so that VB.NyET's Array.Sort would look better, a
> > necessary condition before they would grant permission for you to reveal
> > benchmark results, according to the terms of the .NET Beta 2 SDK EULA?
>
> I was not even aware that I needed permission to write the benchmark in
> .NET. If that's the case, I will be glad to remove it from my site until
> .NET is released. I don't expect a spectacular performance change in the
> released version.
Does your EULA have language equivalent to this:
"5. PERFORMANCE OR BENCHMARK TESTING. You may not disclose the results of
any benchmark test of either the Server Software or Client Software to any
third party without Microsoft's prior written approval."
-- Microsoft .NET Framework SDK Beta 2 EULA
http://msdn.microsoft.com/Downloads/eula_dotNETFrameworkSDK_Beta2.htm
You're so screwed. The entire point of section 5. was to prevent the
disclosure of any less than totally flattering performance test results.
If you don't want to believe me, then perhaps you'll believe MindCraft!
> It's hard to argue that array.Sort is not an advancement.
It isn't, if all it can ever possibly give you is an O(n log n) sort.
> VB6 should have had it's own Sort method built-in too. As array.Sort is a
> general purpose implementation -like my component- it shouldn't prove too
> hard to beat it on performance.
Watch it -- that's not where Microslop wants you to go today.
> It's hard to beat on ease of use though.
Complaints from users about slow-ass sorts more than make up for that.
Speaking of which, your StraightqSort has some other nasty weaknesses,
which were what caused me to suspect the heavy hand of Microshaft.
--
Joe Foster <mailto:jlfoster%40znet.com> Sacrament R2-45 <http://www.xenu.net/>
Willy Van den Driessche
As Any, ByVal Length As Long)
>
> Sub StrSwap(ByRef Str1 As String, ByRef Str2 As String)
> Dim Temp As Long: Temp = StrPtr(Str1)
> RtlMoveMemory ByVal VarPtr(Str1), ByVal VarPtr(Str2), 4
> RtlMoveMemory ByVal VarPtr(Str2), ByVal VarPtr(Temp), 4
> End Sub
bring better performance to the hand-crafted solution. As far as I can
tell, the fastest way I know to sort arrays in VB was described by Matthew
Curland in his book (www.powervb.com) "Sorting, once and for all".
You can always beat my component by an order of magnitude. I can always
improve it so it remains just an order of magnitude. The point of the
component lies in IComparer, ISorthAlgorithm and ISortableContainer. If I
feel like it, I can always write special-purpose implementations of these
interfaces and I will close the gap in performance with the more raw and
special-purpose solutions. But the more special-purpose they are, the less
usable they are. The number of implementations will grow enormously if I
want to serve each special case. What's worse : some combinations of the
triad of interfaces will simply not work.
The article doesn't hide these facts, neither does the performance
comparison article.
You should (an probably will) know that most of the objections that apply to
the sorting component also apply to all other components in general. Every
component makes compromises between ease of use and functionality. I'm
surprised I don't hear these same critiques about something like p.e. the VB
textbox. This also belongs to a component, gives you a lot of functionality
while also hiding a lot but is without any doubt far slower than an
API-created TEXTBOX window. Just as I argue in the article, the creating of
something as simple as a TEXTBOX will require a ton of programming lines.
Chances that you make mistakes are not imaginary. But performance will be
far better and you will have far greater control.
In component-oriented software you sacrifice some performance for ease of
use. If the component isn't easy to use you'll drop it or write it
yourself. Most of the time, however, the performance drop by using a
component is more than compensated for the ease of use. I remember the bad
old days when I had to code texboxes myself. The code is fatter now - I
agree - but I sure like to use a window painter instead of positioning the
textboxes in code. The good thing is that you have a choice. You can do
without components. You càn write everything yourself.
>
> > >Was this overhead
> > > demanded by Microshaft so that VB.NyET's Array.Sort would look better,
a
> > > necessary condition before they would grant permission for you to
reveal
> > > benchmark results, according to the terms of the .NET Beta 2 SDK EULA?
> >
> > I was not even aware that I needed permission to write the benchmark in
> > .NET. If that's the case, I will be glad to remove it from my site
until
> > .NET is released. I don't expect a spectacular performance change in
the
> > released version.
>
> Does your EULA have language equivalent to this:
>
> "5. PERFORMANCE OR BENCHMARK TESTING. You may not disclose the results of
> any benchmark test of either the Server Software or Client Software to any
> third party without Microsoft's prior written approval."
> -- Microsoft .NET Framework SDK Beta 2 EULA
> http://msdn.microsoft.com/Downloads/eula_dotNETFrameworkSDK_Beta2.htm
>
> You're so screwed. The entire point of section 5. was to prevent the
> disclosure of any less than totally flattering performance test results.
> If you don't want to believe me, then perhaps you'll believe MindCraft!
I believe you. I'll take it off today.
>
> > It's hard to argue that array.Sort is not an advancement.
>
> It isn't, if all it can ever possibly give you is an O(n log n) sort.
Joe, I have the impression that you generally critique without giving
alternatives. I can take critique but only if it's justified or if a better
alternative is proposed. I dare you to write a general-purpose sorting
component that has O(n) performance. They didn't do it in C, not in the C++
STL, not in Delphi, not in Modula-II, not in Java and not in .NET. So just
go ahead and claim your fame and amaze us by giving us a general-purpose
sorting component that guarantees O(n) performance. Be sure to mail me when
you're done.
Joe "Nuke Me Xemu" Foster
> > Declare Sub RtlMoveMemory Lib "Kernel32" (ByRef Dest As Any, ByRef Source
> As Any, ByVal Length As Long)
> >
> > Sub StrSwap(ByRef Str1 As String, ByRef Str2 As String)
> > Dim Temp As Long: Temp = StrPtr(Str1)
> > RtlMoveMemory ByVal VarPtr(Str1), ByVal VarPtr(Str2), 4
> > RtlMoveMemory ByVal VarPtr(Str2), ByVal VarPtr(Temp), 4
> > End Sub
> This trick will probably work for the benchmarking code and it will probably
> bring better performance to the hand-crafted solution. As far as I can
> tell, the fastest way I know to sort arrays in VB was described by Matthew
> Curland in his book (www.powervb.com) "Sorting, once and for all".
Yes, it might be interesting to see how his component stacks up against
VB.NyET's Array.Sort, but that's likely not where Microsoft wants you to
go today, eh? It seems his big beef is with the way swapping elements
is normally done, such as your relentless deep-copies of all of varWords'
elements. Or are you "forgetting" StraightqSort's "temp" variable?
> You can always beat my component by an order of magnitude. I can always
> improve it so it remains just an order of magnitude. The point of the
> component lies in IComparer, ISorthAlgorithm and ISortableContainer. If I
> feel like it, I can always write special-purpose implementations of these
> interfaces and I will close the gap in performance with the more raw and
> special-purpose solutions. But the more special-purpose they are, the less
> usable they are. The number of implementations will grow enormously if I
> want to serve each special case. What's worse : some combinations of the
> triad of interfaces will simply not work.
> The article doesn't hide these facts, neither does the performance
> comparison article.
However, I wasn't slamming the raw performance of your components, only
that of your StraightqSort. In addition to slamming StraightqSort, I
criticized your sorting interfaces for being unable to accommodate linear
sorting methods, even on arrays or collections amenable to linear sorts,
not your generic components' speed per se.
> You should (an probably will) know that most of the objections that apply to
> the sorting component also apply to all other components in general. Every
> component makes compromises between ease of use and functionality. I'm
> surprised I don't hear these same critiques about something like p.e. the VB
> textbox. This also belongs to a component, gives you a lot of functionality
> while also hiding a lot but is without any doubt far slower than an
> API-created TEXTBOX window. Just as I argue in the article, the creating of
> something as simple as a TEXTBOX will require a ton of programming lines.
> Chances that you make mistakes are not imaginary. But performance will be
> far better and you will have far greater control.
Nice strawman there. Next, perhaps you will decide that I was "really"
arguing in favor of programming everything from scratch in pure assembly
language?
> In component-oriented software you sacrifice some performance for ease of
> use. If the component isn't easy to use you'll drop it or write it
> yourself. Most of the time, however, the performance drop by using a
> component is more than compensated for the ease of use. I remember the bad
> old days when I had to code texboxes myself. The code is fatter now - I
> agree - but I sure like to use a window painter instead of positioning the
> textboxes in code. The good thing is that you have a choice. You can do
> without components. You càn write everything yourself.
I see you've already decided that I hate all code re-use. >=(
> > You're so screwed. The entire point of section 5. was to prevent the
> > disclosure of any less than totally flattering performance test results.
> > If you don't want to believe me, then perhaps you'll believe MindCraft!
>
> I believe you. I'll take it off today.
After all, Microsoft wouldn't like it if you corrected StraightqSort so
that it actually beat VB.NOT, yes?
> > > It's hard to argue that array.Sort is not an advancement.
> >
> > It isn't, if all it can ever possibly give you is an O(n log n) sort.
>
> Joe, I have the impression that you generally critique without giving
> alternatives.
I have the impression that you generally should ESAD and/or learn to use
search engines such as URL:http://groups.google.com/ .
> I can take critique but only if it's justified or if a better
> alternative is proposed.
Perhaps this will serve to "justify" my claims that your StraightqSort is
straight-up garbage, inviting doubt as to your agenda when you compared
its performance to B#'s Array.Sort:
Sub StrSort(ByRef Strings() As String, ByVal Lower As Long, ByVal Upper As Long, _
Optional ByVal Compare As VbCompareMethod = vbBinaryCompare)
Dim i As Long, j As Long, Pivot As String
Select Case Upper - Lower
Case 1
If StrComp(Strings(Lower), Strings(Upper), Compare) > 0 Then
StrSwap Strings(Lower), Strings(Upper)
End If
Case 2
StrMedian3 Strings(Lower), Strings(Lower + 1), Strings(Upper), Compare
Case Is > 3
StrSwap Pivot, Strings(Lower)
'i = CLng(Rnd * (Upper - Lower - 1)) + Lower + 1 ' Rnd seems expensive
i = RndRange(Lower + 1, Upper)
'Debug.Assert Lower < i And i <= Upper
StrSwap Pivot, Strings(i)
'i = RndRange(Lower + 1, Upper - 2)
'j = RndRange(i + 1, Upper)
'Debug.Assert Lower < i And i < j And j <= Upper
'If i <> Lower + 1 Then StrSwap Strings(i), Strings(Lower + 1)
'If j < Upper Then StrSwap Strings(j), Strings(Upper)
StrMedian3 Strings(Lower + 1), Pivot, Strings(Upper), Compare
'Debug.Assert StrComp(Strings(Lower + 1), Pivot, Compare) <= 0
'Debug.Assert StrComp(Pivot, Strings(Upper), Compare) <= 0
i = Lower
j = Upper + 1
Do
Do
i = i + 1
'Debug.Assert i > Lower And i <= Upper
Loop While StrComp(Strings(i), Pivot, Compare) < 0
Do
j = j - 1
'Debug.Assert j > Lower And j <= Upper
Loop While StrComp(Strings(j), Pivot, Compare) > 0
If j <= i Then Exit Do
'Debug.Assert Lower < i And i < j And j <= Upper
StrSwap Strings(i), Strings(j)
Loop
'Debug.Assert Lower < j And j <= Upper
StrSwap Strings(j), Pivot
StrSwap Strings(Lower), Pivot
If Lower < j - 1 Then StrSort Strings, Lower, j - 1, Compare
If Upper > j + 1 Then StrSort Strings, j + 1, Upper, Compare
Case Else
For i = Lower + 1 To Upper
StrSwap Pivot, Strings(i)
For j = i To Lower + 1 Step -1
'Debug.Assert Lower < j And j <= i And i <= Upper
If StrComp(Pivot, Strings(j - 1), Compare) > 0 Then Exit For
StrSwap Strings(j), Strings(j - 1)
Next
StrSwap Strings(j), Pivot
Next
End Select
'For i = Lower To Upper - 1
' Debug.Assert StrPtr(Strings(i)) <> 0
' Debug.Assert StrPtr(Strings(i + 1)) <> 0
' Debug.Assert StrPtr(Strings(i)) <> StrPtr(Strings(i + 1))
' Debug.Assert StrComp(Strings(i), Strings(i + 1), Compare) <= 0
'Next
End Sub
Private Sub StrMedian3(ByRef Min As String, ByRef Med As String, ByRef Max As String, _
Optional ByVal Compare As VbCompareMethod = vbBinaryCompare)
If StrComp(Med, Min, Compare) < 0 Then StrSwap Med, Min
If StrComp(Med, Max, Compare) > 0 Then StrSwap Med, Max
If StrComp(Med, Min, Compare) < 0 Then StrSwap Med, Min
End Sub
Private Sub StrSwap(ByRef Str1 As String, ByRef Str2 As String)
Dim Temp As Long: Temp = StrPtr(Str1)
RtlMoveMemory ByVal VarPtr(Str1), ByVal VarPtr(Str2), 4
RtlMoveMemory ByVal VarPtr(Str2), ByVal VarPtr(Temp), 4
End Sub
Private Function RndRange(ByVal Min As Long, ByVal Max As Long) As Long
Static k(1 To 17) As Long, v As Long, w As Long
If v = 0 Then
v = (App.ThreadID Xor App.hInstance Xor timeGetTime) And &H7FFFFFFF
Do
w = w + 1
v = (v Mod &H11E56F) * &H727 + 31
k(w) = v
Loop Until w = 17
v = 5
End If
k(v) = (k(v) And &H3FFFFFFF) + k(w) \ 2 + 1
If Min < Max Then
RndRange = k(v) Mod (Max - Min + 1) + Min
ElseIf Min > Max Then
RndRange = k(v) Mod (Min - Max + 1) + Max
Else
RndRange = Min
End If
v = v - 1: If v = 0 Then v = 17
w = w - 1: If w = 0 Then w = 17
End Function
> I dare you to write a general-purpose sorting
> component that has O(n) performance. They didn't do it in C, not in the C++
> STL, not in Delphi, not in Modula-II, not in Java and not in .NET. So just
> go ahead and claim your fame and amaze us by giving us a general-purpose
> sorting component that guarantees O(n) performance. Be sure to mail me when
> you're done.
If I do so, be sure to just go ahead and FOAD, mmmkay?
--
Joe Foster <mailto:jlfoster%40znet.com> L. Ron Dullard <http://www.xenu.net/>
Willy Van den Driessche
Joe "Nuke Me Xemu" Foster
> I'll try to incorporate your code. I'll post when I have new benchmarks.
Of course, you'll also try to "prove" that .NET is still faster, right?
In the meantime, take a look at these stable O(n) in-situ partitioning
algorithms while you drink the Koolaid.NET:
URL:http://staff.cs.utu.fi/~tpasanen/Pubs_of_Tomi_Pasanen.html
URL:http://groups.google.com/groups?selm=20050%40cca.CCA.COM
Do you still insist that an in-place O(n) sort is totally impossible,
even in C, C++ STL, Delphi, Modula-II, Java, or .NET? So just claim
your fame and amaze us by disproving any possible general-purpose
sorting component that guarantees O(n) performance. Be sure to FOAD
when you're done.