Re: non-recursive quicksort for 2-D arrays?

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

OK, now I got you.
You are saying don't use a quicksort as it causes stack problems, but use a Shell Sort, which doesn't
but is nearly as quick.

Actually, I have rarely come across situation where the quicksort didn't work with an error message:
out of stack space.
This was with very large arrays.

I solved this in a way that is most likely completely inefficient, namely run the quicksort on increasingly
bigger parts of the array, but always including LBound.
This is the code:

Function PreSort2DVar(ByRef vArray As Variant, _
ByRef lKey As Long, _
Optional ByRef bAscending As Boolean = True, _
Optional ByRef lLow1 As Long = -1, _
Optional ByRef lHigh1 As Long = -1) As Boolean

'the routine procSort2D can't handle large arrays
'causing an error out of stack space
'this is handled by sorting increasing larger parts
'of the array, so that there is less to be done when
'the whole array gets sorted
'---------------------------------------------------

Dim LR As Long
Dim lPreSorts As Long
Dim lArrayChunk As Long
Dim n As Long

LR = UBound(vArray)

'this value may depend on the hardware
'-------------------------------------
lArrayChunk = 8000

'no need to do pre-sorts
'-----------------------
If LR < lArrayChunk Then
PreSort2DVar = Sort2DVar(vArray, _
lKey, _
bAscending, _
lLow1, _
lHigh1)
Exit Function
End If

lPreSorts = LR \ lArrayChunk

For n = 0 To lPreSorts
If n < lPreSorts Then
'increase the part of the array in steps of lArrayChunk
'------------------------------------------------------
PreSort2DVar = Sort2DVar(vArray, _
lKey, _
bAscending, _
lLow1, _
(n + 1) * lArrayChunk)
Else
'sort the whole array
'--------------------
PreSort2DVar = Sort2DVar(vArray, _
lKey, _
bAscending, _
lLow1, _
lHigh1)
End If
Next

End Function

Where Sort2DVar is a regular quicksort.
Now this is probably crap, although as I say it solves the out of stack problem.
Will have a look at the Shell Sort and see how it performs.


RBS




"J French" <erewhon@xxxxxxxxxx> wrote in message news:445e3973.35789591@xxxxxxxxxxxxxxxxxxxxxxx
On Sun, 7 May 2006 17:23:54 +0100, "RB Smissaert"
<bartsmissaert@xxxxxxxxxxxxxxxx> wrote:

OK, thanks.
What though is the essence of your reply?
Did you think you have code that works faster?

Now I don't know why you were fossicking around finding the mid point

That is not me, I just copied a standard quicksort. I don't think I can
improve on that.

Do not copy anything
- take it, understand it anf /own/ it

What is slightly confusing is that you are talking about pointers and ptr,
but you not dealing
with real pointers (memory addresses) but it looks you mean array indices,
that is array row
numbers.

Stuff memory addresses - one day you will learn that they are not real
(they used to be)

What is the idea of calling that variable L9, I mean what does the 9 stand
for?

Outer most Loop - drummed into me years ago
- if you see another coder using the same convention then ask for a
few more

I also don't follow the ascending/descending stuff

Not sure what the problem is there. Don't I need an argument in my function
to tell if we
are sorting descending or ascending? What is wrong with the way that is done
now, which is just
the standard quicksort in any case.

My rules are very simple
1) Quicksort is crap - it is parasitic on the stack
- it will hit you when you least expect it
2) Simplify
3) Ascending or Descending is just the way you look at things



.

Relevant Pages

  • 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. ... >> Array of UDTs when the sort is completed. ...
    (comp.lang.basic.visual.misc)
  • Re: qsort and arbitrary types
    ... > quicksort algorithm is short enuf to duplicate it into a generic ... the array itself (you can pass a slice which will contain its own ... legitimate indices again is also incomprehensible. ... can be written to use a stack of, at most, the log of the ...
    (comp.lang.fortran)
  • Re: I dont understand the definition of DOES>
    ... on stack on code entry). ... You can use DOES to make ARRAY and then use ARRAY ... CREATE CELLS ALLOT ... First you'd make the code that will execute on the child word. ...
    (comp.lang.forth)
  • how does your language... make a map?
    ... "include"ed in the interpreter for testing. ... Since Forth uses a Last-in-First-out implicit stack, ... variable cols ... I want to create an array that will in the future contain all the ...
    (rec.games.roguelike.development)
  • Re: Globally declared arrays
    ... I noticed that my colleague was declaring local arrays on the stack, ... What is a "global array on ...
    (comp.lang.c)