Original Post
I'm trying to write a program that tests the speeds of three simple sorting algorithms. They are: selection sort, bubble sort, and Insertion Sort. The problem is, I'm not sure if my results are what they should be. I'd really appreciate it if someone could run this code, see how it works on their machine, and possibly inform me of any errors. Basically, there are 9 arrays. The first 3: a1, a2, and a3, are filled with random numbers in the range of 0-4999. The second 3: b1, b2, b3 are filled with numbers already sorted and in correct order. The last 3: c1, c2, c3 are sorted almost entirely, except for the last element which is set to the number 2. I think the sorting functions themselves are correct, so I think the error might lie in the initialization. One of my greates concerns is the fact that the InsertionSort method seems to take 0 milliseconds on an array that is already sorted. Now I know that since the array is already sorted it is going to take less time to sort through it, but shouldn't it take at least a few milliseconds to do this? Anyway, here is the code. I know its a lot to ask, but I've been checking it for like an hour and I can't see what the problem is. Thx, --BioX
[SOURCE]
import java.util.*;
public class Test {
public static void Swap(int a[],int i,int j)
{
int temp = a;
a = a[j];
a[j] = temp;
}
public static void BubbleSort(int myArray[])//NOTE: This bubble sort does not contain the breakout section
{
for(int k = myArray.length -1; k>0; k--)
{
for(int j=0; j<k; j++)
{
if(myArray[j] > myArray[j+1])
{
Swap(myArray, j, j+1);
}
}
}
}
public static void SelectionSort(int myArray[])
{
int minIndex = 0;
for(int i=0; i<myArray.length - 1; i++)
{
for(int j= i + 1; j< myArray.length; j++)
{
if(myArray[j] < myArray[minIndex])
minIndex = j;
}
if(i != minIndex)
{
//swap the numbers
Swap(myArray, i, minIndex);
}
minIndex = i + 1;
}
}
public static void InsertionSort(int myArray[])
{
for(int i=1; i<myArray.length; i++)
{
for(int j=i; j>0; j--)
{
if(myArray[j]<myArray[j-1])
{
Swap(myArray, j, j-1);
}
else
break;
}
}
}
public static void main (String[] args){
Date startTime;
long sortTime;
////////// randomized arrays ///////////
int[] a1 = new int[5000];
int[] a2 = new int[5000];
int[] a3 = new int[5000];
///////// completely sorted /////////////
int[] b1 = new int[5000];
int[] b2 = new int[5000];
int[] b3 = new int[5000];
//////// almost sorted ////////////////////
int[] c1 = new int[5000];
int[] c2 = new int[5000];
int[] c3 = new int[5000];
///////////////////////////////////////////
//set up arrays a1, a2 and a3, where each has 5000 random integers from 1-5000 in it.
//see the bottom of p. 329 for an example of how to do it.
for(int i=0; i<a1.length; i++)
{
a1 = (int)(Math.random() * 5000);
}
for (int j=0;j<a2.length ;j++ )
{
a2[j] = (int)(Math.random() * 5000);
}
for (int k = 0; k<a3.length; k++)
{
a3[k] = (int)(Math.random() * 5000);
}
//set up arrays b1, b2 and b3, where each has 5000 integers from 0-4999 in it, perfectly sorted already.
for(int i=0; i<b1.length; i++)
{
b1 = i;
}
for (int j=0;j<b2.length ;j++ )
{
b2[j] = j;
}
for (int k = 0; k<b3.length; k++)
{
b3[k] = k;
}
//set up arrays c1, c2 and c3, where each has 5000 integers from 0-4999 in it, perfectly sorted already.
//then set the last element of the array to 2. so it'll go 4996, 4997, 4998, 2.
for(int i=0; i<c1.length; i++)
{
c1 = i;
}
for (int j=0;j<c2.length ;j++ )
{
c2[j] = j;
}
for (int k = 0; k<c3.length; k++)
{
c3[k] = k;
}
c1[c1.length - 1] = 2;
c2[c2.length - 1] = 2;
c3[c3.length - 1] = 2;
//for each array, do the sorts and see how long they take.
//test this out going from 0-9 before you do it for 0-4999.
//Used to test the arrays
/*=============================== THE FOLLOWING IS CODE USED TO TEST THE ARRAYS ======================= */
/*
System.out.println("BEFORE SORTS: \n \n \n");
for(int a=0; a<a3.length; a++)
{
System.out.print(a3[a]+ " ");
}
System.out.println("");
for(int a=0; a<b3.length; a++)
{
System.out.print(b3[a]+ " ");
}
System.out.println("");
for(int a=0; a<c3.length; a++)
{
System.out.print(c3[a]+ " ");
}
//////////The selection Sorts//////////
//SelectionSort(a3);
//SelectionSort(b3);
//SelectionSort(c3);
/////////The bubble Sorts////////////
//BubbleSort(a3);
//BubbleSort(b3);
//BubbleSort(c3);
////////the Insertion Sorts
//InsertionSort(a3);
//InsertionSort(b3);
//InsertionSort(c3);
///////////////////////////
System.out.println("");
System.out.println("AFTER SORTS: \n \n \n");
for(int a=0; a<a3.length; a++)
{
System.out.print(a3[a]+ " ");
}
System.out.println("");
for(int a=0; a<b3.length; a++)
{
System.out.print(b3[a]+ " ");
}
System.out.println("");
for(int a=0; a<c3.length; a++)
{
System.out.print(c3[a]+ " ");
}
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("");*/
//======================================== END OF ARRAY TEST CODE ==============================================
//----------------------------------------------
//selection sort
startTime = new Date();
SelectionSort(a1);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Selection sort of a1 took: " + sortTime + " ms.");
startTime = new Date();
SelectionSort(b1);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Selection sort of b1 took: " + sortTime + " ms.");
startTime = new Date();
SelectionSort(c1);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Selection sort of c1 took: " + sortTime + " ms.");
//----------------------------------------------
//bubble sort
startTime = new Date();
BubbleSort(a2);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Bubble sort of a2 took: " + sortTime + " ms.");
startTime = new Date();
BubbleSort(b2);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Bubble sort of b2 took: " + sortTime + " ms.");
startTime = new Date();
BubbleSort(c2);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Bubble sort of c2 took: " + sortTime + " ms.");
//----------------------------------------------
//insertion sort
startTime = new Date();
InsertionSort(a3);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Insertion sort of a3 took: " + sortTime + " ms.");
startTime = new Date();
InsertionSort(b3);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Insertion sort of b3 took: " + sortTime + " ms.");
startTime = new Date();
InsertionSort(c3);
sortTime = (new Date()).getTime() - startTime.getTime();
System.out.println("Insertion sort of c3 took: " + sortTime + " ms.");
}
}
[/SOURCE]