wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> K rank element
        
(Message started by: johny_cage on Nov 24^th, 2007, 1:42pm)

Title: K rank element
Post by johny_cage on Nov 24^th, 2007, 1:42pm

Given an array, find the k-th rank element. (k-th rank element = k-th element from the start in the sorted form(increasing) of the array)
O (nlogn) -- trivial
O(n) -- good

If already asked, plz forgive me. :'(
Although, I searched through the search option :o but nowhere found this question.

Title: Re: K rank element
Post by towr on Nov 25^th, 2007, 7:10am

Quote:

If already asked, plz forgive me.

You're forgiven ;)

Quote:

Although, I searched through the search option :o but nowhere found this question.

The search function of this forum really isn't that good, but it's commendable that you've tried, at least.
You might have better luck with the search option when you search "kth median" or "nth largest" (and possibly similar options)

Quote:

Given an array, find the k-th rank element.

The idea is used/or mentioned in at least these three threads: 1 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102078892), 2 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085), 3 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1066586935).

Title: Re: K rank element
Post by R0B1N on Nov 26^th, 2007, 2:05am

on 11/25/07 at 07:10:05, towr wrote:

The search function of this forum really isn't that good, but it's commendable that you've tried, at least.

Better Idea would be to do a Google search
;D

something like "wwu + kth largest"

Title: Re: K rank element
Post by nitin_162 on Nov 28^th, 2007, 2:54am

Here I am not sorting an array in any case. I am recursively finding the element.

/**
* Finding the Kth rank element in a given array.
* @param arr
* @param k
* @return kth element in the sorted array but not sorting the array.
*/
static int kthElement(int[] arr, int k){
int ret = -1;
int pivot = arr[arr.length / 2];

List<Integer> lList = new ArrayList<Integer>();
List<Integer> rList = new ArrayList<Integer>();
int ele_r = rank(pivot, arr, lList, rList);

//If the computed rank is < k then recursively find the k - ele_r
if(ele_r <= k){
if(ele_r == k){
return arr[ele_r-1];
}
ret = kthElement(popArr(rList), k - ele_r);
} else {
ret = kthElement(popArr(lList), k);
}
return ret;
}

/**
* List to Array of Integers.
* @param list
* @return
*/
static int[] popArr(List<Integer> list) {
int[] arr = new int[list.size()];
for(int i=0; i < list.size(); i++){
arr[i] = list.get(i);
}
return arr;
}

/**
* Computing the element rank in a given array.
* @param num
* @param arr
* @return rank of an element.
*/
static int rank(int num, int[] arr, List<Integer> lList, List<Integer> rList){
int rank = 0;
for(int i=0; i < arr.length; i++){
if(arr[i] < num){
rank++;
lList.add(arr[i]);
}else {
if(arr[i] != num)
rList.add(arr[i]);
}
}
return rank+1;
}

Title: Re: K rank element
Post by nitin_162 on Nov 28^th, 2007, 2:56am

The idea behind the above algo is :

Given an element x ∈ S, we can answer the following query in n − 1 comparisons
Is x the k-th element or is x larger than the k-th element or is x smaller
than the k-th element ?
This is easily done by comparing x with all elements in S −{x} and finding the rank
of x. Using an arbitrary element x as a filter, we can subsequently confine our search
for the k-th element to either
(i) S> = {y ∈ S − {x}|y > x} if R(x, S) < k or
(ii) S< = {y ∈ S − {x}|y < x} if R(x, S) > k
In the fortuitous situation, R(x, S) = k,x is the required element. In case 1, we must
find k′-th element in S> where k′ = k − R(x, S).

Title: Re: K rank element
Post by johny_cage on Nov 29^th, 2007, 1:48am

What is this &#8712 ?

Title: Re: K rank element
Post by nitin_162 on Nov 29^th, 2007, 2:02am

Sorry it is written by mistake.

Title: Re: K rank element
Post by johny_cage on Nov 29^th, 2007, 2:25am

on 11/29/07 at 02:02:32, nitin_162 wrote:

Sorry it is written by mistake.

just correct the explanation, so that we can easily go through it.

Title: Re: K rank element
Post by gotit on Nov 29^th, 2007, 2:53am

Consider the first element of the array as the pivot (say p). Partition the array on p. If the index of p after partitioning is less than k, repeat the partitioning on the right of p. Otherwise do it on the left of p.

Title: Re: K rank element
Post by johny_cage on Nov 29^th, 2007, 3:27am

@gotit
please elaborate your answer, with an example.

Title: Re: K rank element
Post by gotit on Nov 29^th, 2007, 3:53am

I assume array indexing starts from 1. Say you have to find the 4th rank element.

Original array:17,2,16,31,19,27,64. Pivot:17
After partitioning on 17:16,2,17,31,19,27,64

Now the index of 17 is 3 which is smaller than 4. This means that the 4th largest element must be on the right of 17 as all elements to the left are smaller than 17. So we branch to the right and again do the partitioning for that subarray.

Continue doing this partitioning until one of the pivots comes in the 4th index of the array.

Title: Re: K rank element
Post by johny_cage on Nov 29^th, 2007, 4:03am

Please explain on the following array,

n = 7
Array is : 17, 2, 4, 31, 19, 1, 3

Title: Re: K rank element
Post by Tenaliram on Nov 29^th, 2007, 5:43am

You hav array given as

17, 2, 4, 31, 19, 1, 3

Consider you want to find the 4th element

now take 17 as a pivot element.
and partition the array as follows

2, 4, 1, 3, 17, 31, 19

compare the index of 17 i.e. 5 with desired index i.e. 4.
Now we can say that desired element will lie in the left of pivot element .
hence we will partition the left part of the array again with 2 as pivot element.

1, 2, 4,3,17,31,19

again compare index of 2 with 4 .We can say that the desired index value will lie on right of pivot elemnet.
Partitioning right of 2 again by taking 4 as a pivot element..

1,2,3, 4 17,31,19

Now compare the index of pivot element (4) which is 4 and we also desired fourth index value and hence we will stop here.

So the desired 4 th elemnt of the sorted array will be 4.

BTW nice Algo "GOT_IT"

Title: Re: K rank element
Post by gotit on Nov 29^th, 2007, 6:02am

on 11/29/07 at 05:43:53, Tenaliram wrote:

BTW nice Algo "GOT_IT"

This is the standard algo for finding the kth rank element in an array. Its not something I have developed on my own.