Here is a simple Java program that will allow you to run a few different sorting algorithms side by side and compare their speed in milliseconds.
Included algorithms are:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
you can find the .zip to the code here:
https://drive.google.com/file/d/0B9JH6EHjkfuRVXZoaEotdWJzZXM/view?usp=sharing
or copy the following and enter them into your own program.
the code is separated into three files seperated by package sorttestdemo header. the ReadMe.doc
is only included in the .zip file along with a image of the code running on my machine.
/*
* This program (SortTestDemo.java & RandomList.java) was created and writen by Robert Morris on 10/21/2016
* SortList.java was created by Robert Morris with sorting algorithms from:
* https://thilinasameera.wordpress.com/2011/06/01/sorting-algorithms-sample-codes-on-java-c-and-matlab/
* @author Robert Morris
*/
package sorttestdemo;
/**
*
* @author Robert Morris
*/
public class SortTestDemo {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int listSize = 100000; // Initial Starting length of random array to be sorted:
// (WARNING! WILL INCREASE BY A MULTIPLE OF 5, 5 times.)
RandomList randomizedList = new RandomList(); // initialize RandomList Obejct to be operated on.
randomizedList.setListSize(listSize);
randomizedList.randomizeList();
long startTime;
long endTime;
long totalTime;
// copy of list are changed to prevent the usuage of the same array after it has been mutated.
// this could probably be avoided by using a deep copy. But in this case, a simple helper methode worked.
int[] bubbleList = createListCopy(randomizedList.getList());
int[] selectionList = createListCopy(randomizedList.getList());
int[] insertionList = createListCopy(randomizedList.getList());
int[] mergeList = createListCopy(randomizedList.getList());
int[] quickList = createListCopy(randomizedList.getList());
String[] algoNames = {"BubbleSort", "SelectionSort", "InsertionSort", "MergeSort", "QuickSort"};
SortList s = new SortList(); // initialize class of sort methods
// for (int i = 1; i <= 5; i++){
displayLength(listSize);
//randomizedList.displayUnsortedList(); // check to see if list is really randomized
startTime = System.currentTimeMillis();
bubbleList = s.bubbleSort(bubbleList); // Test number 1 (BubbleSort)
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
displayTime(algoNames[0], totalTime); // output time display
//displayList(finalizedList); // check to see if list is really sorted
startTime = System.currentTimeMillis();
selectionList = s.selectionSort(selectionList); // Test number 2 (SelectionSort)
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
displayTime(algoNames[1], totalTime); // output time display
//displayList(finalizedList); // check to see if list is really sorted
startTime = System.currentTimeMillis();
insertionList = s.insertionSort(insertionList); // test number 3 (Insertion Sort)
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
displayTime(algoNames[2], totalTime);different color coated files // output time display
//displayList(finalizedList); // check to see if list is really sorted
startTime = System.currentTimeMillis();
mergeList = s.mergeSort(mergeList); // test number 4 (MergeSort)
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
displayTime(algoNames[3], totalTime); // output time display
//displayList(finalizedList); // check to see if list is really sorted
startTime = System.currentTimeMillis();
quickList = s.quickSort(quickList); // test number 5 (QuickSort)
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
displayTime(algoNames[4], totalTime); // output time display
//displayList(finalizedList); // check to see if list is really sorted
// listSize *= 5; // increase the size of the list by a multiple of 5
// }
}
public static void displayList(int[] theList){
for(int i=0; i<theList.length; i++){
System.out.println(theList[i]);
}
}
public static void displayTime(String algos, long time){
System.out.print("Sort Time of *"+ algos +"* = ");
System.out.print(time);
System.out.println(" Milliseconds. ");
}
public static void displayLength(int listSize){
System.out.println();
System.out.print("Sort Times for a List of Size ---> ");
System.out.print(listSize);
System.out.println(": ");
}
public static int[] createListCopy(int[] oldList){
int[] newList = new int[oldList.length];
for(int i = 0; i < oldList.length; i++ ){
newList[i] = oldList[i];
}
return newList;
}
}
package sorttestdemo;
/**
*
* @author Robert Morris
* This class provides a list of sorting methods that sort arrays
* of integers in accending order.
* The list of sorting methods include:
* BubbleSort, SelectionSort, InsertionSort, MergeSort, QuickSort
*/
public class SortList {
// CONSTRUCTOR
public SortList(){
}
// BUBBLESORT !!!
public int[] bubbleSort(int[] data){
int lenD = data.length;
int tmp = 0;
for(int i = 0;i<lenD;i++){
for(int j = (lenD-1);j>=(i+1);j--){
if(data[j]<data[j-1]){
tmp = data[j];
data[j]=data[j-1];
data[j-1]=tmp;
}
}
}
return data;
}
// SELECTION SORT !!!
public int[] selectionSort(int[] data){
int lenD = data.length;
int j = 0;
int tmp = 0;
for(int i=0;i<lenD;i++){
j = i;
for(int k = i;k<lenD;k++){
if(data[j]>data[k]){
j = k;
}
}
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
return data;
}
// INSERTIONSORT !!!
public int[] insertionSort(int[] data){
int len = data.length;
int key = 0;
int i = 0;
for(int j = 1;j<len;j++){
key = data[j];
i = j-1;
while(i>=0 && data[i]>key){
data[i+1] = data[i];
i = i-1;
data[i+1]=key;
}
}
return data;
}
// MERGE SORT !!!
public int[] mergeSort(int[] data){
int lenD = data.length;
if(lenD<=1){
return data;
}
else{
int[] sorted = new int[lenD];
int middle = lenD/2;
int rem = lenD-middle;
int[] L = new int[middle];
int[] R = new int[rem];
System.arraycopy(data, 0, L, 0, middle);
System.arraycopy(data, middle, R, 0, rem);
L = this.mergeSort(L);
R = this.mergeSort(R);
sorted = merge(L, R);
return sorted;
}
}
public int[] merge(int[] L, int[] R){
int lenL = L.length;
int lenR = R.length;
int[] merged = new int[lenL+lenR];
int i = 0;
int j = 0;
while(i<lenL||j<lenR){
if(i<lenL & j<lenR){
if(L[i]<=R[j]){
merged[i+j] = L[i];
i++;
}
else{
merged[i+j] = R[j];
j++;
}
}
else if(i<lenL){
merged[i+j] = L[i];
i++;
}
else if(j<lenR){
merged[i+j] = R[j];
j++;
}
}
return merged;
}
// QUICKSORT !!!
public int[] quickSort(int[] data){
int lenD = data.length;
int pivot = 0;
int ind = lenD/2;
int i,j = 0,k = 0;
if(lenD<2){
return data;
}
else{
int[] L = new int[lenD];
int[] R = new int[lenD];
int[] sorted = new int[lenD];
pivot = data[ind];
for(i=0;i<lenD;i++){
if(i!=ind){
if(data[i]<pivot){
L[j] = data[i];
j++;
}
else{
R[k] = data[i];
k++;
}
}
}
int[] sortedL = new int[j];
int[] sortedR = new int[k];
System.arraycopy(L, 0, sortedL, 0, j);
System.arraycopy(R, 0, sortedR, 0, k);
sortedL = quickSort(sortedL);
sortedR = quickSort(sortedR);
System.arraycopy(sortedL, 0, sorted, 0, j);
sorted[j] = pivot;
System.arraycopy(sortedR, 0, sorted, j+1, k);
return sorted;
}
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package sorttestdemo;
import java.util.Random;
/**
* This class creates and provides methods for manipulating a random array
* of integers.
* @author Robert Morris
*/
public class RandomList {
public int listSize;
public int[] unsortedList;
public RandomList(){}
public RandomList(int listSize){
setListSize(listSize);
randomizeList();
}
public int[] getList(){
return this.unsortedList;
}
public void setListSize(int newSize){
this.listSize = newSize;
}
public void randomizeList(){
Random r = new Random();
this.unsortedList = new int[this.listSize];
for(int i = 0; i < this.listSize; i++){
this.unsortedList[i] = r.nextInt(1000);
}
}
public void displayUnsortedList(){
for(int j=0; j< this.listSize; j++ ){
System.out.println(this.unsortedList[j]);
}
}
}
No comments:
Post a Comment