There's a well-known order statistic finding algorithm that's O(n) worst
case. See Aho, Hopcroft, and Ulman, DACA. This lets you find the k'th
element for any k. Use it to find the log n'th student and the sqrt n'th
student and then one final O(n) pass to partition the group will do the job.
use the partition process of quicksort. check for the index value of the
pivot item.
As according to the value u traverse only in one direction the average case
will be O(n) but worse case can go to O(n^2)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Ge
I can use bucket sort.But sorting is strictly prohibited. The question gives
a hint which says use your data structure theory to figure this one out.
On Sat, Dec 25, 2010 at 9:16 PM, juver++ wrote:
> You may use bucket sort if extra space is enough.
> Second approach - find (log n)-th statistic
You may use bucket sort if extra space is enough.
Second approach - find (log n)-th statistic and then (log n + sqrt n).
After doing so you may output all students that have marks below
corresponding bounds.
There is O(n) algorithm for finding such values.
--
You received this message because y
