Alternative Methods ...

[T.Jackson]

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

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

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

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

[Ioannis]

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

Ioannis

[T.Jackson]

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

/*   
'********************************************************************************'
'~ 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

[T.Jackson]

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