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