Results 1 to 12 of 12
 11122010, 01:57 AM #1Member
 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<length1;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[idx1]; } 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=lengthtemp;k<length;k++) { for(int z=lengthtemp;z<length1;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 < lengthtemp;j+=5)//watch it closer Tnai lo tov { arr[index]=find[getMedian(j,j+5)]; index++; } j=lengthtemp; if(temp>0) { int idx = (int) Math.ceil(((double)(temp+1)/2)); arr[index]=find[j+idx1]; } //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,INDEXOS_I); } else { return findEBOS(find,start,OS_I,INDEX); } } private static int getMedian(int start,int end) { return start(startend)/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<right1;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 ?
 11122010, 05:05 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,565
 Rep Power
 12
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)
 11122010, 05:14 AM #3
I believe this is the algorithm he's going for: Selection algorithm  Wikipedia, the free encyclopedia
 11122010, 05:32 AM #4Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,565
 Rep Power
 12
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.
 11122010, 07:54 AM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
cenosillicaphobia: the fear for an empty beer glass
 11122010, 11:31 AM #6Member
 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 (ik)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 :(
 11122010, 11:35 AM #7Member
 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
 11122010, 11:47 AM #8Member
 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
 11122010, 01:15 PM #9Member
 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 !
 11122010, 01:58 PM #10Member
 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?
I'm new to Java but I like to help where ever I can. :)
 11122010, 05:13 PM #11Member
 Join Date
 Nov 2010
 Posts
 21
 Rep Power
 0
 11122010, 06:38 PM #12Member
 Join Date
 Oct 2010
 Posts
 94
 Rep Power
 0
Similar Threads

Find All Palindromes
By spleenlol in forum New To JavaReplies: 6Last Post: 02042010, 02:33 AM 
cannot find main  it is there though
By dwilliams in forum New To JavaReplies: 18Last Post: 01112010, 05:01 PM 
Cannot find 'Dataset'
By mgm2010 in forum New To JavaReplies: 2Last Post: 06042009, 11:56 AM 
can't find tamplate.tld anywhere
By amu in forum Advanced JavaReplies: 1Last Post: 10152008, 02:15 PM 
Where to find wsimport
By javaplus in forum Web FrameworksReplies: 1Last Post: 11262007, 09:59 AM
Bookmarks