Alternative Methods ...


Closed Thread
Results 1 to 4 of 4
  1. #1
    T.Jackson's Avatar
    T.Jackson Guest

    Default Alternative Methods ...

    Algorithm to see how many variables are the same ...

    I finished my final unit for Java last week. In the examination there was a question that asked for a method to be written to check to see how many elements in an array contained the same values. Given that there were only 3 elements in the array, the most obvious solution would be to resort to the humble 3-bit truth table and implement an IF statement containing ANDs / ORs. But I wanted to do things differently, I thought outside the square, this is what I came up with ...

    Code:
    public int getObjectsAtSameDistance()
    {   
       int ObjectsSameDistance;
    
       // Scan thru array and see how many objs are at the same distance
       for (int j = 0, j < 2, j++)
       {
          for (int i = j + 1, i < 2, i++)
          {
             if (distances[j] == distances[i])
             {
                objectsSameDistance ++;
                break; 
             }
          }
       }
    
       if (objectsSameDistance > 0)
          objectsSameDistance ++;
    
       return objectsSameDistance;
    }
    The more traditional approach for something like that would be this ...

    Code:
    public int getObjectsAtSameDistance()
    {
       int ObjectsSameDistance;
    
       if (distances[0] == distances[1] && distances[2] == distances[0])
       {
          objectsSameDistance = 3;
       }
       elseif (distances[0] == distances[1] || distances[1] == distances[2] || distances[0] == distances[2])
       {
          objectsSameDistance = 2;
       }
    }
    Doing things like can quickly become unmanagable when there's lots of elements in the array.
    The truth table below supports the solution, whereas a = the first element in the array and c is the last ...

    abc
    000
    001
    010
    011
    100
    101
    110
    111

    I'm fully aware that this is a PBP forum and not Java, so I have ported the code to PBP below for those who wish to give it a whirl ..

    Code:
    Main:  
       objectsSameDistance var byte 
    
       // Scan thru array and see how many objs are at the same distance
       for j = 0 to 2
          for i = j + 1 to 2
             if distances[j] = distances[i] then
                objectsSameDistance = objectsSameDistance + 1
                exit for 
             end if
          next
       next
    Best Regards,

    Trent Jackson
    Last edited by T.Jackson; - 9th June 2008 at 08:57.

  2. #2
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    4,115


    Did you find this post helpful? Yes | No

    Default

    This looks like the old bubble sort algo. I guess that with many elements it will take cosiderable time, won't it?

    Ioannis

  3. #3
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Default

    Quote Originally Posted by Ioannis View Post
    This looks like the old bubble sort algo. I guess that with many elements it will take cosiderable time, won't it?
    Add in a few additional operations and it would become a bubble sort algo ...

    1. Sample compare swap
    2. Adjust pointer position

    I wrote a complete bubble sort program late last year ...

    Code:
    /*   
    '********************************************************************************'
    '~ Bubble sort by Trent Jackson                     08/08/07                                                ' 
    '********************************************************************************'
    */
    
    import java.util.Scanner; 
    import java.util.Random;
    
    public class NumberSort
    {                                                  
       private static final String TERMINATE_PROG = "x";           
       private static int [] rndArray = new int[10000];
       private static Random generator = new Random();
    
       public static void main(String[] args)
       {
          Scanner keyboard = new Scanner(System.in);              
          boolean runprogram = true;                              
          int intkey = 0;                                        
          String strKey;      
          genNums();
                              
          do
          {
             System.out.println();
             System.out.println("******** Number Sorting Algorithm Menu ********");
             System.out.println();
             System.out.println("A. Generate 10,000 new random numbers ...");
             System.out.println();
             System.out.println("B. Sort numbers & display time taken in mS");
             System.out.println();
             System.out.println("C. Print array of numbers");
             System.out.println();
             System.out.println("X. Exit the program");
             System.out.println();
             System.out.println("***********************************************");
             System.out.println();
             System.out.print("Select one of the options above: ");
             
             strKey = keyboard.next(); // Wait for menu selection                                      
               
             if (strKey.equalsIgnoreCase(TERMINATE_PROG))         
             {
                runprogram = false; 
             }
             else if (strKey.equalsIgnoreCase("a"))
             {
                genNums();
             }
             else if (strKey.equalsIgnoreCase("b"))
             {
                sortNums();
             }
             else if (strKey.equalsIgnoreCase("c"))
             {
                printNums();
             }
    
          } while (runprogram == true); // Go back and do it all again until user quits ...
       }
    
       public static void genNums()
       {
          // Generate 10K worth of random numbers between (0 - 32,000)
          for (int i = 0; i < 10000; i++)
          {
             int rnd = generator.nextInt(32000);
             rndArray[i] = rnd;
          }
       } 
    
       public static void sortNums()
       {
       // Basically, this algo will sort an array of numbers from lowest to highest.
       // Starting from the top of the list we attempt to find a larger number than
       // the one at the bottom. When we do, we swap them. 
    
          int compareA = 0;
          int compareB = 0;
          int swap = 0;
          int arrayPos = 0; 
          int i = 9999;
          int j = 0;
    
          // Sample system time 
          long startTime = System.currentTimeMillis ();
    
          do
          {
             compareA = rndArray[i]; 
             for (j = arrayPos; j < i; j++)
             {
                compareB = rndArray[j];
                if (compareB > compareA)
                {
                   swap = rndArray[i];
                   rndArray[i] = compareB;
                   rndArray[j] = swap;
                   arrayPos = j;
                   break;
                } 
             } 
             if (j == i)
             {
                i --;
                arrayPos = 0;
             }
          } while (i > 0); 
    
          // Sample system time  & calc time elapsed 
          long finishTime = System.currentTimeMillis ();
          System.out.println();
          System.out.println("Time taken to sort 10,000 unordered numbers: " + (finishTime - startTime) + "mS");
       }
    
       public static void printNums()
       {
          for (int i = 0; i < 9999; i++)
          {
             System.out.println(rndArray[i]);
          }
       }
    }
    Regards,

    Trent Jackson

  4. #4
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Default

    Code:
    public int getObjectsAtSameDistance()
    {   
       int ObjectsSameDistance;
    
       // Scan thru array and see how many objs are at the same distance
       for (int j = 0, j < 2, j++)
       {
          for (int i = j + 1, i < 2, i++)
          {
             if (distances[j] == distances[i])
             {
                objectsSameDistance ++;
                break; 
             }
          }
       }
    
       if (objectsSameDistance > 0)
          objectsSameDistance ++;
    
       return objectsSameDistance;
    }
    There is actually a problem with this method the more I think about it. Works fine for 3 elements / variables, but what if there's say 5, whereas 3 of them = 100 and the other 2 = 50 -- which ones do we report as being the same? As is the code will return a value of 5.

    The solution is limited but not flawed ...

    Trent Jackson
    Last edited by T.Jackson; - 9th June 2008 at 13:16.

Similar Threads

  1. Alternative for 'printf'
    By Sach_1979 in forum General
    Replies: 1
    Last Post: - 25th September 2009, 01:02
  2. Pulsin alternative
    By sbobowski in forum mel PIC BASIC Pro
    Replies: 5
    Last Post: - 4th October 2008, 09:21
  3. Alternative to the H44780 lcd controler
    By Sphere in forum Off Topic
    Replies: 11
    Last Post: - 31st July 2008, 19:17
  4. alternative Pin for vref
    By ruijc in forum General
    Replies: 6
    Last Post: - 15th January 2008, 10:46
  5. Alternative power supply
    By The Master in forum Off Topic
    Replies: 2
    Last Post: - 20th November 2007, 13:38

Members who have read this thread : 0

You do not have permission to view the list of names.

Posting Permissions

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