Task #1 Program: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort and Qui
ID: 3907448 • Letter: T
Question
Task #1 Program: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort and Quick Sort to sort a list of n elements. Carry out a complete test of your sorting algorithms with n -10,000, 20,000, 50,000, 100,000,.. (up to the largest size of n that your computer can handle You should stop the program for any method if it takes more than 10 minutes to run). Report your results. (80 Pts) Task #2 For each sorting method, record the sorting time for different number of n and then graph time vs. n. Write a detailed report and compare all sorting algorithms in terms of their time complexities. Explain if your empirical results are consistent with theories. (20 Pts)Explanation / Answer
Solution:
The java code for given problem is shown below:
//Include library
import java.util.Random;
//Define a class
public class SortAlgorithmTime
{
static int[][] lst = new int[6][];
static int[] list1 = new int[10000];
static int[] list2 = new int[20000];
static int[] list3 = new int[100000];
static int[] list4 = new int[200000];
static int[] list5 = new int[1000000];
static int[] list6 = new int[2000000];
public static void main(String[] args)
{
String algorithm[] = { "Bubble Sort", "Insertion Sort", "Merge Sort", "Selection Sort","Quick sort"};
String size[]={"10,000", "20,000", "100,000", "200,000", "1,000,000", "2,000,000" };
displayList();
generatelist();
lst[0] = list1;
lst[1] = list2;
lst[2] = list3;
lst[3] = list4;
lst[4] = list5;
lst[5] = list6;
for (int li = 0; li < lst.length; li++)
{
System.out.println();
System.out.println("List size : "+size[li]);
System.out.println();
for (int lj = 0; lj < 5; lj++)
{
System.out.println("Trail : "+ (lj+1));
System.out.println();
System.out.print("The Elapsedtime of "+algorithm[0]+" algorthim for "+size[li]+" items is = ");
BubbleSortTimingForAllList(lst[li]);
System.out.print("The Elapsedtime oof "+algorithm[1]+" algorthim for "+size[li]+" items is = ");
InsertionSortTimingForAllList(lst[li]);
System.out.print("The Elapsedtime of "+algorithm[2]+" algorthim for "+size[li]+" items is = ");
MergeSortTimingForAllList(lst[li]);
System.out.print("The Elapsedtime of "+algorithm[3]+" algorthim for "+size[li]+" items is = ");
SelectionSortTimingForAllList(lst[li]);
}
}
}
public static void generatelist()
{
list1 = generateRandomNumbers(10000, 10000);
list2 = generateRandomNumbers(20000, 20000);
list3 = generateRandomNumbers(100000, 100000);
list4 = generateRandomNumbers(200000, 200000);
list5 = generateRandomNumbers(1000000, 1000000);
list6 = generateRandomNumbers(2000000, 2000000);
}
public static void displayList()
{
System.out.println("1. List of 10000 nmbrs.");
System.out.println("2. List of 20000 nmbrs.");
System.out.println("3. List of 100000 nmbrs.");
System.out.println("4. List of 200000 nmbrs.");
System.out.println("5. List of 1000000 nmbrs.");
System.out.println("6. List of 2000000 nmbrs.");
}
public static void quickSortTimingForAllList(int[] lst)
{
stpWtch timer = new stpWtch();
timer.start();
quickSort(lst);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Quick sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ lst.length +".");
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
public static void MergeSortTimingForAllList(int[] lst)
{
stpWtch timer = new stpWtch();
timer.start();
mergeSort(lst);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Merge sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ lst.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
public static void BubbleSortTimingForAllList(int[] lst)
{
stpWtch timer = new stpWtch();
timer.start();
bubbleSort(lst);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Bubble sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ lst.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
public static void SelectionSortTimingForAllList(int[] lst)
{
stpWtch timer = new stpWtch();
timer.start();
selectionSort(lst);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Selection sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ lst.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
public static void InsertionSortTimingForAllList(int[] lst)
{
stpWtch timer = new stpWtch();
timer.start();
insertionSort(lst);
timer.stop();
if(timer.getElapsedTime()==900000)
{
System.out.println("The Insertion sort takes more than 15 minutes.");
System.out.println("The size of the data set is "+ lst.length +".");
System.exit(0);
}
else
{
System.out.println(timer.getElapsedTime() + " milliseconds");
}
}
public static int[] generateRandomNumbers(int length, int range)
{
int[] randNums = new int[length];
Random lrnd = new Random();
for (int li = 0; li < length; ++li)
{
randNums[li] = lrnd.nextInt(range);
}
return randNums;
}
public static int[] quickSort(int[] nmbrs)
{
qckSrtHlpr(nmbrs, 0, nmbrs.length - 1);
return nmbrs;
}
private static void qckSrtHlpr(int[] nmbrs, int lint, int lst)
{
if ((lst - lint) < 1 || (lst < 0))
{
return;
}
int pvtIndx = partitionList(nmbrs, lint, lst);
qckSrtHlpr(nmbrs, lint, pvtIndx - 1);
qckSrtHlpr(nmbrs, pvtIndx + 1, lst);
}
private static int partitionList(int[] nmbrs, int lint, int lst)
{
int lstAssgndPs = lint;
for (int li = lint; li < lst; ++li)
{
if (nmbrs[li] < nmbrs[lst])
{
swap(nmbrs, lstAssgndPs, li);
++lstAssgndPs;
}
}
swap(nmbrs, lst, lstAssgndPs);
return lstAssgndPs;
}
public static int[] mergeSort(int[] nmbrs)
{
return mergeSortHelper(nmbrs, 0, nmbrs.length - 1);
}
private static int[] mergeSortHelper(int[] nmbrs, int lint, int lst)
{
if ((lst - lint) == 0)
{
return new int[] { nmbrs[lst] };
}
int mid = (lst + lint) / 2;
int[] sbLst1 = mergeSortHelper(nmbrs, lint, mid);
int[] sbLst2 = mergeSortHelper(nmbrs, mid + 1, lst);
return merge(sbLst1, sbLst2);
}
private static int[] merge(int[] sbLst1, int[] sbLst2)
{
int[] result = new int[sbLst1.length + sbLst2.length];
int sb1Frst = 0;
int sb2Frst = 0;
for (int li = 0; li < result.length; ++li)
{
if (sb1Frst == sbLst1.length)
{
result[li] = sbLst2[sb2Frst++];
} else if (sb2Frst == sbLst2.length)
{
result[li] = sbLst1[sb1Frst++];
} else if (sbLst1[sb1Frst] <= sbLst2[sb2Frst])
{
result[li] = sbLst1[sb1Frst++];
} else
{
result[li] = sbLst2[sb2Frst++];
}
}
return result;
}
public static int[] bubbleSort(int[] nmbrs)
{
boolean swppd = false;
do
{
swppd = false;
for (int li = 0; li < (nmbrs.length - 1); ++li)
{
if (nmbrs[li] > nmbrs[li + 1])
{
swap(nmbrs, li, li + 1);
swppd = true;
}
}
} while (swppd);
return nmbrs;
}
public static int[] selectionSort(int[] nmbrs)
{
for (int li = 0; li < nmbrs.length - 1; ++li)
{
int mnIndx = li;
for (int lj = li + 1; lj < nmbrs.length; ++lj)
{
if (nmbrs[lj] < nmbrs[mnIndx])
mnIndx = lj;
}
swap(nmbrs, mnIndx, li);
}
return nmbrs;
}
public static int[] insertionSort(int[] nmbrs)
{
for (int li = 1; li < nmbrs.length; ++li)
{
for (int lj = li; lj > 0; --lj)
{
if (nmbrs[lj] < nmbrs[lj - 1])
{
swap(nmbrs, lj, lj - 1);
} else
{
break;
}
}
}
return nmbrs;
}
private static void swap(int[] nmbrs, int li, int lj)
{
int tmp = nmbrs[li];
nmbrs[li] = nmbrs[lj];
nmbrs[lj] = tmp;
}
}
//Define a class
class stpWtch
{
private long elpsdTme;
private long strtTme;
private boolean isRnnng;
public stpWtch()
{
reset();
}
public void start()
{
if (isRnnng)
return;
isRnnng = true;
strtTme = System.currentTimeMillis();
}
public void stop()
{
if (!isRnnng)
return;
isRnnng = false;
long endTme = System.currentTimeMillis();
elpsdTme = elpsdTme + endTme - strtTme;
}
public long getElapsedTime()
{
if (isRnnng)
{
long endTme = System.currentTimeMillis();
return elpsdTme + endTme - strtTme;
}
else
return elpsdTme;
}
public void reset()
{
elpsdTme = 0;
isRnnng = false;
}
}
Sample Output:
E:javajdk1.6.0_11in>javac SortAlgorithmTime.java
E:javajdk1.6.0_11in>java SortAlgorithmTime
1. List of 10000 nmbrs.
2. List of 20000 nmbrs.
3. List of 100000 nmbrs.
4. List of 200000 nmbrs.
5. List of 1000000 nmbrs.
6. List of 2000000 nmbrs.
List size : 10,000
Trail : 1
The Elapsedtime of Bubble Sort algorthim for 10,000 items is = 294 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Merge Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Selection Sort algorthim for 10,000 items is = 83 milliseconds
Trail : 2
The Elapsedtime of Bubble Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Selection Sort algorthim for 10,000 items is = 78 milliseconds
Trail : 3
The Elapsedtime of Bubble Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Selection Sort algorthim for 10,000 items is = 66 milliseconds
Trail : 4
The Elapsedtime of Bubble Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Selection Sort algorthim for 10,000 items is = 67 milliseconds
Trail : 5
The Elapsedtime of Bubble Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 10,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 10,000 items is = 1 milliseconds
The Elapsedtime of Selection Sort algorthim for 10,000 items is = 66 milliseconds
List size : 20,000
Trail : 1
The Elapsedtime of Bubble Sort algorthim for 20,000 items is = 1298 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 20,000 items is = 3 milliseconds
The Elapsedtime of Selection Sort algorthim for 20,000 items is = 267 milliseconds
Trail : 2
The Elapsedtime of Bubble Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 20,000 items is = 2 milliseconds
The Elapsedtime of Selection Sort algorthim for 20,000 items is = 279 milliseconds
Trail : 3
The Elapsedtime of Bubble Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 20,000 items is = 3 milliseconds
The Elapsedtime of Selection Sort algorthim for 20,000 items is = 280 milliseconds
Trail : 4
The Elapsedtime of Bubble Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 20,000 items is = 2 milliseconds
The Elapsedtime of Selection Sort algorthim for 20,000 items is = 269 milliseconds
Trail : 5
The Elapsedtime of Bubble Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 20,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 20,000 items is = 2 milliseconds
The Elapsedtime of Selection Sort algorthim for 20,000 items is = 296 milliseconds
List size : 100,000
Trail : 1
The Elapsedtime of Bubble Sort algorthim for 100,000 items is = 35951 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 100,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 100,000 items is = 15 milliseconds
The Elapsedtime of Selection Sort algorthim for 100,000 items is = 6586 milliseconds
Trail : 2
The Elapsedtime of Bubble Sort algorthim for 100,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 100,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 100,000 items is = 15 milliseconds
The Elapsedtime of Selection Sort algorthim for 100,000 items is = 6653 milliseconds
Trail : 3
The Elapsedtime of Bubble Sort algorthim for 100,000 items is = 0 milliseconds
The Elapsedtime oof Insertion Sort algorthim for 100,000 items is = 0 milliseconds
The Elapsedtime of Merge Sort algorthim for 100,000 items is = 15 milliseconds
The Elapsedtime of Selection Sort algorthim for 100,000 items is =
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.