# Thread: Can someone help me with Find OS_K alg

1. Member
Join Date
Nov 2010
Posts
21
Rep Power
0

## Can someone help me with Find OS_K alg

Java Code:
```
public class findElementByOrderStatistic {

public static Comparable findEBOS(Comparable[] find,int start,int end,int INDEX){
int length;
int temp=0;
Comparable x;
int OS_I;

length=end;

if(length < 6){
for(int i=start;i<length;i++)
for(int j=start;j<length-1;j++)
{
if(find[j].compareTo(find[j+1])>0)
{
Comparable temp1 = find[j+1];
find[j+1]=find[j];
find[j]=temp1;
}
}
int idx = (int) Math.ceil(((double)(length+1)/2));
return find[idx-1];
}

temp=length%5;

int smart=0;
if(temp>0)
{
smart=(length/5) +1;
}
else
smart=length/5;

Comparable [] arr = new Comparable[smart];

/*getting medians of group*/
int i;
/*sorting groups of 5*/
for( i=start;i<((length)-temp);i+=5)
{
Sort5(find,start+i,start+i+5);
}
if(temp>0){ //for the reminded
for(int k=length-temp;k<length;k++)
{
for(int z=length-temp;z<length-1;z++)
if(find[z].compareTo(find[z+1])>0)
{
Comparable temp1=find[z+1];
find[z+1]=find[z];
find[z]=temp1;
}
}
}
//will make array of the medians
int index=0;
int j;
for(j =0 ; j < length-temp;j+=5)//watch it closer    Tnai lo tov
{
arr[index]=find[getMedian(j,j+5)];
index++;
}
j=length-temp;
if(temp>0)
{
int idx = (int) Math.ceil(((double)(temp+1)/2));
arr[index]=find[j+idx-1];
}

//arr is array of medians

//find median of medians by recursion call to this function
x = findEBOS(arr,0,arr.length,INDEX);

OS_I =Partition(find,x);//wtf is wrong here?

if(OS_I==INDEX)
{
return x;
}

else if(INDEX>OS_I)
{
return findEBOS(find,OS_I,length,INDEX-OS_I);
}
else
{
return	findEBOS(find,start,OS_I,INDEX);
}
}

private static int getMedian(int start,int end)
{
return start-(start-end)/2;
}

public static int Partition(Comparable[] array,Comparable x)
{

int counter=0;

for(int i=0; i<array.length;i++)
{
if(x.compareTo(array[i])>0)
counter++;
}
return counter;
}

private static void Sort5 (Comparable[] array,int left , int right)
{
Comparable temp;
for (int i = left ; i<right;i++)
{
for(int j =left;j<right-1;j++)
{
if(array[j].compareTo(array[j+1])>0)
{
temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}
}```

it works when array size less than 6
it kinda works when array size less equal than 8

and it throws exception when the array size bigger than 8

some have any ideas ?

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
14
some have any ideas ?

If I understand what findEBOS() is trying to do: use a list, extract the sublist, sort it and return the appropriate element.

If you are trying to implement a particular algorithm could you describe what it is? (google EBOS or OS_K didn't turn up anything illuminating)

3. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
14
I see. If that's the problem then you can omit the "sublist" bit (as that page says "Selection can be reduced to sorting by sorting the list and then extracting the desired element.").

I would guess the OP is trying to implement the Blum, Floyd, Pratt, Rivest and Tarjan algorithm.

@OP: is that what you are trying to do? What is the problem: "kinda works" isn't very descriptive? If there are runtime exceptions that you can't understand, post the stack trace and say which line of your code it is referring to.

4. Originally Posted by Bored2
Java Code:
```	private static int getMedian(int start,int end)
{
return start-(start-end)/2;
}```
No matter the correctness of the rest of your code, the above part is certainly very cryptic. You'll never understand it when you reread it after some time. Better burry it in comments. It almost fooled me ;-)

kind regards,

Jos

5. Member
Join Date
Nov 2010
Posts
21
Rep Power
0
The algorithm i trying to implement is :

Java Code:
```1.		Divide n elements into groups of 5
2.		Find median of each group
3.		Use Select() recursively to find median x of the n/5 	medians
4.		Partition the n elements around x.
5.		Let k = rank(x)
6.		if (i == k) then
return x
7.		if (i < k) then
use Select() recursively to find ith smallest element in first partition
8.		else
use Select() recursively to find (i-k)th smallest element in last partition```

yes its a Blum, Floyd, Pratt, Rivest and Tarjan algorithm.

kind'a works means it is works no errors but it returns junk values :(

6. Member
Join Date
Nov 2010
Posts
21
Rep Power
0
I googled it but i couldn't find a psudo code of it

because I doubt that I missing something :-X

7. Member
Join Date
Nov 2010
Posts
21
Rep Power
0
When array bigger than 8 it throws exeption "StackOverFlowError" at line 6

so the function enters endless recursion

8. Member
Join Date
Nov 2010
Posts
21
Rep Power
0
it is Over thanks for help !!
i just missed the line that I have to arrange the Find array that X will be in the middle of it.

if you want the working code PM me !

9. Member
Join Date
Oct 2010
Posts
94
Rep Power
0
Just one question for my personal interest: is this Comparable class you are using the result of the one you were designing in your other thread? So you changed the compareTo method to take one argument?

10. Member
Join Date
Nov 2010
Posts
21
Rep Power
0

## Yes :)

Originally Posted by venerik
Just one question for my personal interest: is this Comparable class you are using the result of the one you were designing in your other thread? So you changed the compareTo method to take one argument?
Yes it is my class ...

I implemented the both ways ...(overloaded)
if that Lector wouldn't be able to decrease my Grade :) (He would it the silly way he took it the silly way)

11. Member
Join Date
Oct 2010
Posts
94
Rep Power
0
Ah, very well.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•