Re: Fastest Date Sort

With the QuickSort currently working in my app, I have to assume I'm not
giving it anything that would cause this 'stack' overflow concern. Hope it
never comes up, because this Quicksort is really kicking some timing butt!
My program never ran so dang fast.

On the subject of using Index sorting, was my assumption correct on its use?
I didn't hear back from anyone on that.

I've gone through my application and changed all the string types to date
for variables that store dates. It certainly is cleaner, as I can do a
direct date subtraction (ie dNextDate - dYesterdaysDate) rather than having
to use DateValue(dNextDate) - DateValue(dYesterdaysDate). Bet I probably
saved a ton of overhead getting rid of all those DateValue()'s, right?

:-)


"Steve Gerrard" <mynamehere@xxxxxxxxxxx> wrote in message
news:dOidnSg1AudWhzrenZ2dnUVZ_s-dnZ2d@xxxxxxxxxxxxxx
>
> "J French" <erewhon@xxxxxxxxxx> wrote in message
> news:43a68c45.866064740@xxxxxxxxxxxxxxxxxxxxxxx
>> On Sun, 18 Dec 2005 16:44:03 -0800, "Steve Gerrard"
>> <mynamehere@xxxxxxxxxxx> wrote:
>>
>>
>> I'll jump in here
>>
>> The Interface idea is a good one
>>
> Thought you might like that...
>
>> If Rick R does not want to change code elsewhere then he would
>> probably still benefit a lot from sorting Indexes then rebuild the
>> Array of UDTs when the sort is completed.
>>
>> The extra overhead would not be that bad, the real killer is swapping
>> the records during the Sort.
>>
>
> True. In fact, I have a production app that does this very thing. It is
> definitely more efficent to sort an index and then rebuild the main array
> with it, especially if the array is of a complex type.
>
>> QuickSort makes me nervous, Stack usage depends entirely on the order
>> of the data, so if the data were in perfect reverse order ....
>
> Actually, reverse order is not a problem, it divides quite neatly into
> halves, quarters, etc. It would take more than a billion elements to force
> it past 32 layers deep in the stack.
>
> There are, however, theoretical orders that could generate very deep
> stacking. They are extremely rare. I have tested 100 million elements, and
> gotten a maximum stack depth of 58. If you ever encounter an array order
> that pushes the quick sort past a depth of 100, I would buy a lottery
> ticket the same day, since by all rights, you should win that as well.
>
> Some stats on quick sort versus shell sort, in a compiled exe, for what
> it's worth:
>
> 1 million random longs, range 1 to 10:
> Quick Sort: 967,563 swaps; 0.125 seconds; stack depth 30
> Shell Sort: 4,268,109 swaps; 0.266 seconds; stack depth 1
>
> 1 million random longs, range 1 to 100,000,000:
> Quick Sort: 4,621,243 swaps; 0.250 seconds; stack depth 49
> Shell Sort: 45,450,199 swaps; 0.938 seconds; stack depth 1
>
> I have to say, though, for most purposes, the Shell sort result is plenty
> fast enough.
>
>


.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Quicksort
    ... worth the bother of ensuring that the stack space was adequate. ... is to set a reasonable maximum on the recursion ... case, I usually use either selection sort or a bubble sort variant, such as ... suited to the problem areas of quicksort). ...
    (comp.programming)
  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... fully recursive form to the semi recursive form of quicksort by ... If the compiler does tail recursion elimination, ... quicksort, in the average case, is one of the fastest sort algos. ...
    (comp.programming)
  • Re: non-recursive quicksort for 2-D arrays?
    ... You are saying don't use a quicksort as it causes stack problems, but use a Shell Sort, which doesn't ... bigger parts of the array, ... Dim lArrayChunk As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: non-recursive quicksort for 2-D arrays?
    ... I just copied a standard quicksort. ... with real pointers but it looks you mean array indices, ... MsgBox "Start Sort" ... Ptr= Hld ...
    (microsoft.public.vb.general.discussion)