Hi all,
Quoted from Wikipedia:
>Pigeonhole sorting, also known as count sort, is a sorting algorithm that
>takes linear time (Θ(n)), which is the best possible performance for a sorting
>algorithm since >one must inevitably look at each of the elements being sorted
>at least once, regardless o
Yeah, after finding the k-th element there is no need for further
partitioning. This is logically true indeed.
But in this case, I guess you have to do it for determining who'll get
the Samosas and who the Gulabjamuns !!.
--~--~-~--~~~---~--~~
You received this m
Do we have to partition after finding the kth element ? Will the Array not
be partitioned when the base condition is met ?
Amal.
On 3/16/07, Rajiv Mathews <[EMAIL PROTECTED]> wrote:
>
>
> On 3/16/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
> >
> > How would the median algorithm get the top
Yeah the average case is O(n) and worst case is O(n^2) as rightfully
pointed out. But I still feel that this would be the best solution as
the P(worst case) is quite less.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Gro
yes thats what i meant. its not just for median but can be used to find any
nth order statistic(median is just a special case)
On 3/16/07, Rajiv Mathews <[EMAIL PROTECTED]> wrote:
>
>
> On 3/16/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
> >
> > How would the median algorithm get the top k e
On 3/16/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
> How would the median algorithm get the top k elements?
>
I think what he meant was, use the median by parting-in-5 algorithm to
find the kth largest element. This can be done in O(n).
Then just partition around this element to get the
How would the median algorithm get the top k elements?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this
cant we just use the linear median algorithm to select the top k elements?
On 3/15/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
>
> Yes..but in the worst case you could partition the list into 1 and
> n-1...we cannot say this deterministically. The average case is O(n)
> but worst case woul
Yes..but in the worst case you could partition the list into 1 and
n-1...we cannot say this deterministically. The average case is O(n)
but worst case would still be O(n^2)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Gro
You could try the quick-sort algo with these further modifications :
every time you partition the list (assuming ascending) you leave out
the entire working for the right hand part iff the size of the left
hand part is >= m (m is the top m elements that you need). NB : Here
left hand part indicate
radix sort would take O(nk) time in terms of the number of digits. And
infact sorting is a much bigger problem than what we need. All that we
need is the top k elements of an n element list.
A strategy would be to use fibonacci heaps that have O(1) Decrease
key. You can construct a heap out of t
you can sort the students list according to marks in o(n) time by using
RADIX SORT.
On 3/14/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
> Dean of Computer Science department wants to keep the motivation
> levels of students of data structure course high by giving incentives.
> He has sugg
12 matches
Mail list logo
