
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
Bookmarks