> Followup: "quickselect" is the name of this:
>
>
http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm
Hi Jens,
I've coded this algorithm up with a few minimal test cases:
https://github.com/dyoo/quick-select
It should do the trick, though you'll need
> Hmmm... the behavior of quicksort almost feels like what you want; in
> the optimal case, it's supposed to choose the median, and then
> partition elements into things bigger or less than the median. You
> might be able to get away with an in-place quicksort that's stops
> early. Your problem d
On Fri, Mar 16, 2012 at 3:26 PM, Jens Axel Søgaard
wrote:
> 2012/3/16 Danny Yoo :
>
>> Hmmm... the behavior of quicksort almost feels like what you want; in
>> the optimal case, it's supposed to choose the median, and then
>> partition elements into things bigger or less than the median. You
>> m
2012/3/16 Danny Yoo :
> Hmmm... the behavior of quicksort almost feels like what you want; in
> the optimal case, it's supposed to choose the median, and then
> partition elements into things bigger or less than the median. You
> might be able to get away with an in-place quicksort that's stops
>
Do you mean a quicksort that performs only the filtering functionality around a
pivot? QS is 'cheap' because the assumption is that you can pick a good pivot.
What if you also pass along weights that tell you how many of the numbers you
want in each part? It's 1/2 and 1/2 initially but as you
On Fri, Mar 16, 2012 at 4:11 PM, Jens Axel Søgaard
wrote:
> 2012/3/16 Danny Yoo :
>
>> Hmmm... Questions: why is a list-based approach a requirement?
>
> Er. Well. A vector based solution would be fine too.
>
>> Do the
>> numbers share a special characteristic, such as being densely packed
>> into
2012/3/16 Danny Yoo :
> Hmmm... Questions: why is a list-based approach a requirement?
Er. Well. A vector based solution would be fine too.
> Do the
> numbers share a special characteristic, such as being densely packed
> into a tight range? If so, bucket sorting could be applied to get
> fast
On Fri, Mar 16, 2012 at 3:49 PM, Jens Axel Søgaard
wrote:
> Hi All,
>
> I am looking for a list based algorithm, that solves this problem:
>
> Input: A list xs of numbers.
> Output: Two lists of numbers ys and zs whose
> lengths differ at most by one, and:
>
> for all
Hi All,
I am looking for a list based algorithm, that solves this problem:
Input:A list xs of numbers.
Output: Two lists of numbers ys and zs whose
lengths differ at most by one, and:
for all y in yz and z in zs:y<=z
A simple solution using sort is
(s
9 matches
Mail list logo
