order statistics

hi, Have a problem where i want to write a program to find the ith order statistic of a data set consisting of character and their occurences. For example i have a data set consiting of B,A,C,A,B,C,A,D; here i have A with 3 occurences,B with 2 occurences C with 2 occurences and D with on occurrence. So they can be group in pairs (charaters,Number of occurences); so here we have (A,3),(B,2),(C,2) and (D,1). Assuming than k is the number of these pairs, how can i find the ith of the data set in O(k) where k is the number of pairs. Well i thought i could sort the element based their number of occurence and find their ith smallest elements but i am not sure that can work.

any help?

On what programming language you need to write code?

Quote:

---

Originally Posted by bestellen

On what programming language you need to write code?

---

in c#. the alogorithm will be fine. i will write the code myself

Quote:

---

Originally Posted by sanchez_masherano

how can i find the ith of the data set

---

What does this means? What is it that you want to find?

Quote:

---

Originally Posted by razzle

What does this means? What is it that you want to find?

---

i have to find the kth smallest element from that data set.

Quote:

---

Originally Posted by sanchez_masherano

i have to find the kth smallest element from that data set.

---

I think you're too imprecise in your problem description but okay, finding the k'th smallest element in a sequence is a known problem called selection and is described here for example,

http://en.wikipedia.org/wiki/Selection_algorithm