[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]Sorting algorithms code
Author
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
On an already sorted input, insertion sort runs in O(n) by simply checking each element against the previous one. Doing 5000 checks is really quick with a good optimizing compiler. (EDIT: now that you mention it, I'm not sure if this is the case in Java).
Your best bet is to increase the size of your arrays (250.000 entries, for instance) and see what happens.
Your best bet is to increase the size of your arrays (250.000 entries, for instance) and see what happens.
Well, I haven't run your code, but I can tell you what you should expect as I have implementations of these algorithms (and many MANY more) in C++.
InsertionSort for the in-order and almost in-order cases should be by far the fastest. Yes it should take less than a millisecond!
This would be followed eventually by bubble sort on the sorted and nearly sorted arrays.
Next would come all cases of selection sort at about the same time, as well as insertion sort on random data.
Last of all would be bubble sort for random data.
However your third time runs with a 2 at the end are not necessary as they will give times very close to the sorted array time trials. What you might like to try instead though is a reverse-sorted array, as this will be much slower than all of the previous cases for bubble sort and insertion sort, but will be about the same for selection sort.
Your algorithm implementations look pretty good, except that your insertion sort has a large inefficiency in that it inserts each item into the sorted portion by a lot of swapping, rather than simply saving the item to be inserted, moving the necessary items along by one, and copying the original item into it's place. Remember that a swap is actually THREE copies, and the portion of the array needing moving could be moved with 1 copy per item instead of three.
Here is my C++ implementation on insertion sort (I'll leave translation for you):
InsertionSort for the in-order and almost in-order cases should be by far the fastest. Yes it should take less than a millisecond!
This would be followed eventually by bubble sort on the sorted and nearly sorted arrays.
Next would come all cases of selection sort at about the same time, as well as insertion sort on random data.
Last of all would be bubble sort for random data.
However your third time runs with a 2 at the end are not necessary as they will give times very close to the sorted array time trials. What you might like to try instead though is a reverse-sorted array, as this will be much slower than all of the previous cases for bubble sort and insertion sort, but will be about the same for selection sort.
Your algorithm implementations look pretty good, except that your insertion sort has a large inefficiency in that it inserts each item into the sorted portion by a lot of swapping, rather than simply saving the item to be inserted, moving the necessary items along by one, and copying the original item into it's place. Remember that a swap is actually THREE copies, and the portion of the array needing moving could be moved with 1 copy per item instead of three.
Here is my C++ implementation on insertion sort (I'll leave translation for you):
template <class T, class Size>void InsertionSort(T a[], Size n) { C_ASSERT((Size)-1 < 0); //'Size' must be a signed type for (Size i = 1; i < n; ++i) { //check if the item needs inserting first (eliminates redundant copying) if (a < a) {<br> Size j = i - <span class="cpp-number">1</span>;<br> <span class="cpp-keyword">const</span> T tempItem = a<span style="font-weight:bold;">;<br> <span class="cpp-comment">//move items along while looking for the correct place</span><br> <span class="cpp-keyword">do</span> {<br> a[j + <span class="cpp-number">1</span>] = a[j];<br> –j;<br> } <span class="cpp-keyword">while</span> ((j >= <span class="cpp-number">0</span>) && (tempItem < a[j]));<br> <span class="cpp-comment">//copy item into position</span><br> a[j + <span class="cpp-number">1</span>] = tempItem;<br> }<br> }<br>}<br></pre></div><!–ENDSCRIPT–>
Instead of increasing the size of the array to be sorted try to run the same sort function a lot of times.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
