Re: Finding Percentiles WITHOUT Sorting

From: Randy Howard (randyhoward_at_FOOverizonBAR.net)
Date: 08/22/04 

Date: Sun, 22 Aug 2004 00:57:07 GMT

In article <eo2dnVGuOoXhcLrcRVn-qw@giganews.com>, anon@inter.net says...
> Sadly the data itself is 4 bytes, so a 4-byte index will simply double the
> memory... might as well just sort a copy of the original array -- which I
> don't have the memory for :(

I missed the original post, so I don't have the full context of what you
are trying to do, however, can you save the existing array to disk, then
sort it, then re-read the original file after you find the other data you
want?

Also, there are techniques for sorting very large data stores with
limited memory. 5.4 of Knuth Volume 3 might be a good place to
start your research.

>
> <Michael.Lacy.junk@colostate.edu> wrote in message
> news:41277ea5@news.ColoState.EDU...
> > In sci.stat.math Anonymous <anon@inter.net> wrote:
> > > I don't want to sort the ORIGINAL array. I wouldn't mind sorting a COPY,
> > > except that I don't have enough memory for both at the same time...
> hence my
> > > problem.
> >
> > Dumb simple idea, but not suggested yet: If you can afford tacking an
> > original sequence number (say 4 bytes) onto each record, you could
> > quicksort to get the percentiles, and then quicksort on the sequence
> > number to restore the data.
> > 

-- 
Randy Howard
To reply, remove FOOBAR.

Relevant Pages

  • Re: Finding Percentiles WITHOUT Sorting
    ... > don't have the memory for:( ... I missed the original post, so I don't have the full context of what you ... >> quicksort to get the percentiles, and then quicksort on the sequence ...
    (comp.programming)
  • Memory Problem w/ASUS A7V133 MB in XP Pro - repost
    ... Original post 3/2/08 ... The problem begins when I try to upgrade the memory using 512MB ... it would not boot with one 256 + one512. ... a different scenario with more helpful info I hope. ...
    (microsoft.public.windowsxp.hardware)
  • Re: Parallel Quicksort version 1.01 ...
    ... However maybe quicksort is interesting for multi-threading because it uses ... Maybe memory cells even need to be 8 bytes but I don't think so but I am not ... the hardware changes then the code should still force it upon the ...
    (alt.comp.lang.borland-delphi)
  • Re: Meaning of in-place; was fast stable sort
    ... [snip excellent counter-arguments] ... Now, having said all the above, I will modify my position. ... additional memory" with an implied "of some kind" without ... "quicksort is in-place whereas merge sort is not", ...
    (comp.programming)
  • Re: User exception
    ... I stay by my original post - you have memory corruption. ... only LPSTR variables and I do no calls to SysFreeString. ...
    (microsoft.public.win32.programmer.ole)