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

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

Ioannis

Quote:

---

Originally Posted by Ioannis

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

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