Sorting in vbscript.

I think this post maybe also is relevant this group
here:

http://www.911cd.net/forums//index.p...dpost&p=151633

Benny

"Benny Pedersen" <b.pedersen@xxxxxx> wrote in message
news:e76a3bd0-ee72-4eba-b83e-1abe54f685e2@xxxxxx

> Sorting in vbscript.
>
> I think this post maybe also is relevant this group
> here:
>
> http://www.911cd.net/forums//index.p...dpost&p=151633
>
> Benny

Interesting. The code is hard to follow and seems busy, but surprisingly
turns out to be faster than the standard bubble sort (by better than a
factor of 2).

--
Richard Mueller
MVP Directory Services
Hilltop Lab - http://www.rlmueller.net
--

On Nov 29, 3:44*am, "Richard Mueller [MVP]" <rlmueller-
nos...@xxxxxx> wrote:

> "Benny Pedersen" <b.peder...@xxxxxx> wrote in message
>
> news:e76a3bd0-ee72-4eba-b83e-1abe54f685e2@xxxxxx
>

> > Sorting in vbscript.

>

> > I think this post maybe also is relevant this group
> > here:

>

> >http://www.911cd.net/forums//index.p...25&view=findpo...

>

> > Benny

>
> Interesting. The code is hard to follow and seems busy, but surprisingly
> turns out to be faster than the standard bubble sort (by better than a
> factor of 2).
>
> --
> Richard Mueller
> MVP Directory Services
> Hilltop Lab -http://www.rlmueller.net
> --

Thanks Mueller for notice my post!

It was very clear in my head when I wrote it, and I still remember the
principle, but unfortunately it is now less clear than the day I wrote
them.
Strange is that I already somehow knew that someone maybe replied
something like you did, so I couldn't sleep and turned on my computer
again...
(Time is here 4:32 AM). I'm still sure that it can't be done faster.
except for the last loop, which should be possible to get rid of...

Sorry about my english (my upstairs neighbour helped me with my
previous post in the other forum).

Benny,
www.fineraw.com

"Richard Mueller [MVP]" <rlmueller-nospam@xxxxxx> wrote in
message news:esDeFycUJHA.6060@xxxxxx

>
> "Benny Pedersen" <b.pedersen@xxxxxx> wrote in message
> news:e76a3bd0-ee72-4eba-b83e-1abe54f685e2@xxxxxx

>> Sorting in vbscript.
>>
>> I think this post maybe also is relevant this group
>> here:
>>
>> http://www.911cd.net/forums//index.p...dpost&p=151633
>>
>> Benny

>
> Interesting. The code is hard to follow and seems busy, but surprisingly
> turns out to be faster than the standard bubble sort (by better than a
> factor of 2).

Is a fast sorting algorithm the new "better mousetrap"? If so, the OP should
beware of the path being beaten to his door!

When I was teaching a Fortran course, I came up with a method for optimizing
a bubble sort that took advantage of the data set not being completely
unsorted. It was a bit slower when dealing with data that was pre-sorted in
reverse order, but much faster when the data was not that badly unsorted. If
I recall correctly, it too was about twice as fast on average.

But... the code was somewhat arbitrarily complex. No path was beaten to my
door, and I abandoned it before ever puttiing it to real use.

/Al

>
> --
> Richard Mueller
> MVP Directory Services
> Hilltop Lab - http://www.rlmueller.net
> --
>
>

"Benny Pedersen" <b.pedersen@xxxxxx> wrote in message
news:94f04753-c311-499a-bc3a-5ed054fafca9@xxxxxx
On Nov 29, 3:44 am, "Richard Mueller [MVP]" <rlmueller-
nos...@xxxxxx> wrote:

> "Benny Pedersen" <b.peder...@xxxxxx> wrote in message
>
> news:e76a3bd0-ee72-4eba-b83e-1abe54f685e2@xxxxxx
>

> > Sorting in vbscript.

>

> > I think this post maybe also is relevant this group
> > here:

>

> >http://www.911cd.net/forums//index.p...25&view=findpo...

>

> > Benny

>
> Interesting. The code is hard to follow and seems busy, but surprisingly
> turns out to be faster than the standard bubble sort (by better than a
> factor of 2).
>
> --
> Richard Mueller
> MVP Directory Services
> Hilltop Lab -http://www.rlmueller.net
> --

Thanks Mueller for notice my post!

It was very clear in my head when I wrote it, and I still remember the
principle, but unfortunately it is now less clear than the day I wrote
them.

===> LOL, one of the practicalities that tends to offset coding brilliance.
You need to learn how precious that flash of insight is and find a way to
document how and why your logic works before you, inevitably, forget...

But I must say that I am impressed with your code. Quoting from the your
911cd post: "I have only attended elementary school, and that my knowlede
about computers, script, etc., are all home learned".

<===

Strange is that I already somehow knew that someone maybe replied
something like you did, so I couldn't sleep and turned on my computer
again...
(Time is here 4:32 AM). I'm still sure that it can't be done faster.
except for the last loop, which should be possible to get rid of...

===> well, maybe that is the solution: don't do it faster, just get up
earlier in the morning!

Sorry about my english (my upstairs neighbour helped me with my
previous post in the other forum).

===> the apology is unnecessary.

/Al

In microsoft.public.scripting.vbscript message <e76a3bd0-ee72-4eba-b83e-
1abe54f685e2@xxxxxx>, Fri, 28 Nov 2008 15:36:12,
Benny Pedersen <b.pedersen@xxxxxx> posted:

>Sorting in vbscript.
>
>I think this post maybe also is relevant this group
>here:
>
>http://www.911cd.net/forums//index.p...&view=findpost
>&p=151633

It would be more legible if posted in News.

Apparently, it takes items in turn and inserts them in a new array in
their correct position with respect to what is already there, moving
higher ones up.

For N items of input originally in a random order, it will take time
proportional to N*N, unless the language used can optimise the actual
moving-up time (Pascal has a fast MOVE(src, dst, amount)). Good
routines take time N*log(N).

Read <http://en.wikipedia.org/wiki/Sort_(computing)> and its linked
articles, and maybe <URL:http://www.merlyn.demon.co.uk/js-order.htm>.

--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF2 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

On Nov 30, 12:43*am, Dr J R Stockton <j...@xxxxxx> wrote:

> In microsoft.public.scripting.vbscript message <e76a3bd0-ee72-4eba-b83e-
> 1abe54f68...@xxxxxx>, Fri, 28 Nov 2008 15:36:12,
> Benny Pedersen <b.peder...@xxxxxx> posted:
>

> >Sorting in vbscript.

>

> >I think this post maybe also is relevant this group
> >here:

>

> >http://www.911cd.net/forums//index.p...&view=findpost
> >&p=151633

>
> It would be more legible if posted in News.
>
> Apparently, it takes items in turn and inserts them in a new array in
> their correct position with respect to what is already there, moving
> higher ones up.
>
> For N items of input originally in a random order, it will take time
> proportional to N*N, unless the language used can optimise the actual
> moving-up time (Pascal has a fast MOVE(src, dst, amount)). *Good
> routines take time N*log(N).
>
> Read <http://en.wikipedia.org/wiki/Sort_(computing)> and its linked
> articles, and maybe <URL:http://www.merlyn.demon.co.uk/js-order.htm>.
>
> --
> *(c) John Stockton, nr London UK. * ?...@xxxxxx * * IE7 FF2 Op9 Sf3
> *news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
> *<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
> *<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

Thanks all for your replies.

The extra array isn't needed. I ony add the extra array to avoid your
"that is hard code", but since some of you found it
hard anyway, so I removed the extra array.
YES, it is still the fastest sorting function, which exist...
That's because of the DO-Loop, which is the secret. All the other code
can be done in many ways with only low improvement.

Also one could skip lowerbound (arr(0)) and start with 1 instead of
zero, which I like better

Something like below.

Benny
PS: included two other functions:
One to test about sorted.
One to build the array using random numbers instead of reverse order.
BTW. If you compare with other sorting function, just remember that
the other should not be written i COM or WSF Java, etc...,
but instead other code comparing should be written in the same
language (obvious).


option explicit
dim MsgTitle, NumberOfElements
const BeginWithOne= true' Skip arr(0)

NumberOfElements= 40 ' Skip zero, use arr(1)...arr(4)

NumberOfElements= NumberOfElements +1
dim arr: reDim arr(NumberOfElements-1)

ArrRandom arr, NumberOfElements, "max value:",50
arr(0)= -50

MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
BeginWithOne)
MsgTitle= MsgTitle & ". Executed: False."
msgBox join(arr), 4096, MsgTitle

:::::::: BennySort arr

MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
BeginWithOne)
MsgTitle= MsgTitle & ". Executed: True."
msgBox join(arr), 4096, MsgTitle

sub BennySort(byRef arr)
dim H, A, L, e, i
for i= 2 to uBound(arr)
H= i: A= H\2: L= 0

e= arr(i)
do: if e < arr(A) then
H= A
else L= A
end if
A= (L+H)\2
loop until A=L

for H= i to A+2 step-1: arr(H)= arr(H-1): next
arr(H)= e
next
end sub

function Sorted(byVal arr, ignore, byVal boolMsg, BeginWithOne)
dim i, ret: ret= "Sortorder: True "
for i= 1 -BeginWithOne to uBound(arr)
if arr(i-1) > arr(i) then ret= "Sortorder: False ": exit for
next
if boolMsg then
on error resume next: i= i +(0 < inStr(ret,": T"))
msgBox left(ret & vbLf &"arr(" _
& i-1 &") > arr(" & i &")"& vbLf & arr(i-1) _
&" > "& arr(i),16-96*(1 > inStr(ret,": T"))), 4096
if err then msgBox ret, 4096: err.clear
end if
Sorted= ret
end function

sub ArrRandom(byRef arr, NumberOfElements, ignore, MaxRandomValue)
dim i: for i= 0 to NumberOfElements -1
randomize: arr(i)= int((MaxRandomValue * rnd) +1)
next
end sub

On Dec 1, 9:11*am, Benny Pedersen <b.peder...@xxxxxx> wrote:

> On Nov 30, 12:43*am, Dr J R Stockton <j...@xxxxxx> wrote:
>
>
>
>
>

> > In microsoft.public.scripting.vbscript message <e76a3bd0-ee72-4eba-b83e-
> > 1abe54f68...@xxxxxx>, Fri, 28 Nov 2008 15:36:12,
> > Benny Pedersen <b.peder...@xxxxxx> posted:

>

> > >Sorting in vbscript.

>

> > >I think this post maybe also is relevant this group
> > >here:

>

> > >http://www.911cd.net/forums//index.p...&view=findpost
> > >&p=151633

>

> > It would be more legible if posted in News.

>

> > Apparently, it takes items in turn and inserts them in a new array in
> > their correct position with respect to what is already there, moving
> > higher ones up.

>

> > For N items of input originally in a random order, it will take time
> > proportional to N*N, unless the language used can optimise the actual
> > moving-up time (Pascal has a fast MOVE(src, dst, amount)). *Good
> > routines take time N*log(N).

>

> > Read <http://en.wikipedia.org/wiki/Sort_(computing)> and its linked
> > articles, and maybe <URL:http://www.merlyn.demon.co.uk/js-order.htm>.

>

> > --
> > *(c) John Stockton, nr London UK. * ?...@xxxxxx * *IE7 FF2 Op9 Sf3
> > *news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
> > *<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
> > *<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

>
> Thanks all for your replies.
>
> The extra array isn't needed. I ony add the extra array to avoid your
> "that is hard code", but since some of you found it
> hard anyway, so I removed the extra array.
> YES, it is still the fastest sorting function, which exist...
> That's because of the DO-Loop, which is the secret. All the other code
> can be done in many ways with only low improvement.
>
> Also one could skip lowerbound (arr(0)) and start with 1 instead of
> zero, which I like better
>
> Something like below.
>
> Benny
> PS: included two other functions:
> One to test about sorted.
> One to build the array using random numbers instead of reverse order.
> BTW. If you compare with other sorting function, just remember that
> the other should not be written i COM or WSF Java, etc...,
> but instead other code comparing should be written in the same
> language (obvious).
>
> option explicit
> dim MsgTitle, NumberOfElements
> const BeginWithOne= true' Skip arr(0)
>
> NumberOfElements= 40 *' Skip zero, use arr(1)...arr(4)
>
> NumberOfElements= NumberOfElements +1
> dim arr: reDim arr(NumberOfElements-1)
>
> ArrRandom arr, NumberOfElements, "max value:",50
> arr(0)= -50
>
> MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
> BeginWithOne)
> MsgTitle= MsgTitle & ". Executed: False."
> msgBox join(arr), 4096, MsgTitle
>
> :::::::: BennySort arr
>
> MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
> BeginWithOne)
> MsgTitle= MsgTitle & ". Executed: True."
> msgBox join(arr), 4096, MsgTitle
>
> sub BennySort(byRef arr)
> * dim H, A, L, e, i
> * for i= 2 to uBound(arr)
> * * *H= i: A= H\2: L= 0
>
> * * *e= arr(i)
> * * *do: if e < arr(A) then
> * * * * * *H= A
> * * * * *else L= A
> * * * * *end if
> * * * * *A= (L+H)\2
> * * *loop until A=L
>
> * * *for H= i to A+2 step-1: arr(H)= arr(H-1): next
> * * *arr(H)= e
> * next
> end sub
>
> function Sorted(byVal arr, ignore, byVal boolMsg, BeginWithOne)
> * dim i, ret: ret= "Sortorder: True "
> * for i= 1 -BeginWithOne to uBound(arr)
> * * if arr(i-1) > arr(i) then ret= "Sortorder: False ": exit for
> * next
> * if boolMsg then
> * * * *on error resume next: i= i +(0 < inStr(ret,": T"))
> * * * *msgBox left(ret & vbLf &"arr(" _
> * * * *& i-1 &") > arr(" & i &")"& vbLf & arr(i-1) _
> * * * *&" > "& arr(i),16-96*(1 > inStr(ret,": T"))), 4096
> * * * *if err then msgBox ret, 4096: err.clear
> * end if
> * Sorted= ret
> end function
>
> sub ArrRandom(byRef arr, NumberOfElements, ignore, MaxRandomValue)
> * dim i: for i= 0 to NumberOfElements -1
> * * *randomize: arr(i)= int((MaxRandomValue * rnd) +1)
> * next
> end sub- Hide quoted text -
>
> - Show quoted text -

Maybe we could construct a function, which is able to
make all possibilities, e.g. with the number 1 and 2,
there would be 4 combinations, but 1 and 1, would be
2 and 2 equal:

1 2
2 1
1 1
2 2

then construct the same but use three numbers instead of 2, and so

1 1 2
1 2 1
2 1 1
1 2 3
.... and so on


It would be enought to test using let say max. 8 numbers,

1 2 3 4 5 6 7 8

(The function maybe also should return the number of combinations
each.)

I would like such a function that could be used to make a final test.
I think it is called a brute force technique, or something like...

Benny

"Benny Pedersen" <b.pedersen@xxxxxx> wrote in message
news:bdc32bc5-d24c-46c0-a383-8764496a12a3@xxxxxx
On Nov 30, 12:43 am, Dr J R Stockton <j...@xxxxxx> wrote:

> In microsoft.public.scripting.vbscript message <e76a3bd0-ee72-4eba-b83e-
> 1abe54f68...@xxxxxx>, Fri, 28 Nov 2008 15:36:12,
> Benny Pedersen <b.peder...@xxxxxx> posted:
>

> >Sorting in vbscript.

>

> >I think this post maybe also is relevant this group
> >here:

>

> >http://www.911cd.net/forums//index.p...&view=findpost
> >&p=151633

>
> It would be more legible if posted in News.
>
> Apparently, it takes items in turn and inserts them in a new array in
> their correct position with respect to what is already there, moving
> higher ones up.
>
> For N items of input originally in a random order, it will take time
> proportional to N*N, unless the language used can optimise the actual
> moving-up time (Pascal has a fast MOVE(src, dst, amount)). Good
> routines take time N*log(N).
>
> Read <http://en.wikipedia.org/wiki/Sort_(computing)> and its linked
> articles, and maybe <URL:http://www.merlyn.demon.co.uk/js-order.htm>.
>
> --
> (c) John Stockton, nr London UK. ?...@xxxxxx IE7 FF2 Op9 Sf3
> news:comp.lang.javascript FAQ
> <URL:http://www.jibbering.com/faq/index.html>.
> <URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates,
> sources.
> <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items,
> links.

Thanks all for your replies.

The extra array isn't needed. I ony add the extra array to avoid your
"that is hard code", but since some of you found it
hard anyway, so I removed the extra array.
YES, it is still the fastest sorting function, which exist...
That's because of the DO-Loop, which is the secret. All the other code
can be done in many ways with only low improvement.

Also one could skip lowerbound (arr(0)) and start with 1 instead of
zero, which I like better

Something like below.

Benny
PS: included two other functions:
One to test about sorted.
One to build the array using random numbers instead of reverse order.
BTW. If you compare with other sorting function, just remember that
the other should not be written i COM or WSF Java, etc...,
but instead other code comparing should be written in the same
language (obvious).


option explicit
dim MsgTitle, NumberOfElements
const BeginWithOne= true' Skip arr(0)

NumberOfElements= 40 ' Skip zero, use arr(1)...arr(4)

NumberOfElements= NumberOfElements +1
dim arr: reDim arr(NumberOfElements-1)

ArrRandom arr, NumberOfElements, "max value:",50
arr(0)= -50

MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
BeginWithOne)
MsgTitle= MsgTitle & ". Executed: False."
msgBox join(arr), 4096, MsgTitle

:::::::: BennySort arr

MsgTitle= Sorted(arr, "is sorted? show a message is:", false,
BeginWithOne)
MsgTitle= MsgTitle & ". Executed: True."
msgBox join(arr), 4096, MsgTitle

sub BennySort(byRef arr)
dim H, A, L, e, i
for i= 2 to uBound(arr)
H= i: A= H\2: L= 0

e= arr(i)
do: if e < arr(A) then
H= A
else L= A
end if
A= (L+H)\2
loop until A=L

for H= i to A+2 step-1: arr(H)= arr(H-1): next
arr(H)= e
next
end sub

function Sorted(byVal arr, ignore, byVal boolMsg, BeginWithOne)
dim i, ret: ret= "Sortorder: True "
for i= 1 -BeginWithOne to uBound(arr)
if arr(i-1) > arr(i) then ret= "Sortorder: False ": exit for
next
if boolMsg then
on error resume next: i= i +(0 < inStr(ret,": T"))
msgBox left(ret & vbLf &"arr(" _
& i-1 &") > arr(" & i &")"& vbLf & arr(i-1) _
&" > "& arr(i),16-96*(1 > inStr(ret,": T"))), 4096
if err then msgBox ret, 4096: err.clear
end if
Sorted= ret
end function

sub ArrRandom(byRef arr, NumberOfElements, ignore, MaxRandomValue)
dim i: for i= 0 to NumberOfElements -1
randomize: arr(i)= int((MaxRandomValue * rnd) +1)
next
end sub

----------

In the last Sub, Randomize should only be called once. For example:
=====
Sub ArrRandom(ByRef arr, NumberOfElements, ignore, MaxRandomValue)
Dim i
Randomize
For i = 0 To NumberOfElements -1
arr(i) = Int((MaxRandomValue * Rnd()) + 1)
Next
End Sub
=======
The above produces integers from 1 to MaxRandomValue. Rnd is not a very good
random number generator (although good enough for this purpose), but calling
Randomize repeatedly makes it worse.

--
Richard Mueller
MVP Directory Services
Hilltop Lab - http://www.rlmueller.net
--

"Benny Pedersen" <b.pedersen@xxxxxx> wrote in message
news:bdc32bc5-d24c-46c0-a383-8764496a12a3@xxxxxx

> The extra array isn't needed. I ony add the extra array to avoid your
> "that is hard code", but since some of you found it
> hard anyway, so I removed the extra array.
> YES, it is still the fastest sorting function, which exist...
> That's because of the DO-Loop, which is the secret. All the other code
> can be done in many ways with only low improvement.

Benny, thanks for the sorting routine. Quite impressive!

The double array version works well for me, but the single array version
does not appear to sort the first element of the array. In the example you
posted, you set the first element to -50, so it naturally comes before all
of the random positive numbers, but if I change it from -50 to 50, it still
shows up as the first element in the array after sorting.