Results 1 to 12 of 12
  1. #1
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Exclamation 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. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    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. #3
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    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.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,784
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Bored2 View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Default

    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 :(

  7. #7
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Default

    I googled it but i couldn't find a psudo code of it

    because I doubt that I missing something :-X

  8. #8
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Default

    When array bigger than 8 it throws exeption "StackOverFlowError" at line 6

    so the function enters endless recursion

  9. #9
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Default

    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 !

  10. #10
    venerik is offline Member
    Join Date
    Oct 2010
    Posts
    94
    Rep Power
    0

    Default

    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. :)

  11. #11
    Bored2 is offline Member
    Join Date
    Nov 2010
    Posts
    21
    Rep Power
    0

    Default Yes :)

    Quote Originally Posted by venerik View Post
    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)

  12. #12
    venerik is offline Member
    Join Date
    Oct 2010
    Posts
    94
    Rep Power
    0

    Default

    Ah, very well.
    I'm new to Java but I like to help where ever I can. :)

Similar Threads

  1. Find All Palindromes
    By spleenlol in forum New To Java
    Replies: 6
    Last Post: 02-04-2010, 03:33 AM
  2. cannot find main - it is there though
    By dwilliams in forum New To Java
    Replies: 18
    Last Post: 01-11-2010, 06:01 PM
  3. Cannot find 'Dataset'
    By mgm2010 in forum New To Java
    Replies: 2
    Last Post: 06-04-2009, 12:56 PM
  4. can't find tamplate.tld anywhere
    By amu in forum Advanced Java
    Replies: 1
    Last Post: 10-15-2008, 03:15 PM
  5. Where to find wsimport
    By javaplus in forum Web Frameworks
    Replies: 1
    Last Post: 11-26-2007, 10:59 AM

Posting Permissions

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