Can someone please explain to me what this code does and how. Code: import java.
ID: 3694784 • Letter: C
Question
Can someone please explain to me what this code does and how.
Code:
import java.util.Arrays;
import java.util.Random;
public class TestSorting {
public static void main(String args[]) {
int[] size = { 10, 50, 100, 500, 1000 };
for (int j = 0; j < size.length; j++) {
int[] a = new int[size[j]];
a = (int[]) createPartiallySortedArray(size[j],0,size[j]);
StopWatch stopWatch = new StopWatch();
stopWatch.start();
System.out.println("Array of Size " + size[j]);
QuickSort.sort(a);
stopWatch.stop();
stopWatch.showElapsedTime();
}
}
/***
*
* @param size
* @return
*/
public static int[] createRandomArray(int size) {
int[] result = new int[size];
Random randomGenerator = new Random();
for (int i = 0; i < size; i++) {
result[i] = randomGenerator.nextInt(size * 100);
}
return result;
}
/***
*
* @param size
* @return
*/
public static int[] createSortedArray(int size) {
return createPartiallySortedArray(size, 0, size);
}
/**
*
* @param size
* @param from
* @param to
* @return
*/
public static int[] createPartiallySortedArray(int size, int from, int to) {
int[] result = createRandomArray(size);
Arrays.sort(result, from, to);
return result;
}
}
public class StopWatch {
private long startTime;
private long elapsedTime;
private boolean isRunning;
public StopWatch() {
this.reset();
}
public void start() {
if (this.isRunning) {
return;
}
this.isRunning = true;
this.startTime = System.currentTimeMillis();
}
public void stop() {
if (!this.isRunning) {
return;
}
this.isRunning = false;
long endTime = System.currentTimeMillis();
this.elapsedTime += endTime - this.startTime;
}
public long getElapsedTime() {
if (this.isRunning) {
long endTime = System.currentTimeMillis();
return this.elapsedTime + endTime - this.startTime;
}
return this.elapsedTime;
}
public void reset() {
this.elapsedTime = 0;
this.isRunning = false;
}
public void showElapsedTime() {
System.out.println("Elapsed time: " + this.elapsedTime + " milliseconds.");
}
}
Sorting.java:
public class Sorting {
private String name;
Sorting(String name) {
this.name = name;
}
/**
* @return the name
*/
public String getName() {
return name;
}
/**
* @param name
* the name to set
*/
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Sorting [name=" + name + "]";
}
}
QuickSort.java
public class QuickSort extends Sorting {
QuickSort() {
super("Quick Sort");
}
/**
*
* @param array
*/
public static void sort(int[] array) {
sort(array, 0, array.length - 1);
}
/**
*
* @param array
* @param from
* @param to
*/
public static void sort(int[] array, int from, int to) {
if (from >= to) {
return;
}
int p = partition(array, from, to);
sort(array, from, p - 1);
sort(array, p + 1, to);
}
/**
*
* @param array
* @param from
* @param to
* @return
*/
private static int partition(int[] array, int l, int h) {
int x = array[h]; // pivot
int i = (l - 1); // Index of smaller element
for (int j = l; j <= h - 1; j++) {
// If current element is smaller than or equal to pivot
if (array[j] <= x) {
i++; // increment index of smaller element
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[h];
array[h] = temp;
return (i + 1);
}
}
MergeSort.java
public class MergeSort extends Sorting {
MergeSort() {
super("Merge Sort");
}
/***
*
* @param mergeSortArray
*/
public static void mergeSort(int[] mergeSortArray) {
if (mergeSortArray.length <= 1) {
return;
}
int[] first = new int[mergeSortArray.length / 2];
int[] second = new int[mergeSortArray.length - first.length];
for (int i = 0; i < first.length; i++) {
first[i] = mergeSortArray[i];
}
for (int i = 0; i < second.length; i++) {
second[i] = mergeSortArray[i + first.length];
}
mergeSort(first);
mergeSort(second);
merge(first, second, mergeSortArray);
}
/**
*
* @param mergeSortArray
*/
public static void sort(int[] mergeSortArray) {
if (mergeSortArray.length <= 1) {
return;
}
int[] first = new int[mergeSortArray.length / 2];
int[] second = new int[mergeSortArray.length - first.length];
for (int i = 0; i < first.length; i++) {
first[i] = mergeSortArray[i];
}
for (int i = 0; i < second.length; i++) {
second[i] = mergeSortArray[first.length + i];
}
sort(first);
sort(second);
merge(first, second, mergeSortArray);
}
/**
*
* @param first
* @param second
* @param mergeSortArray
*/
private static void merge(int[] first, int[] second, int[] mergeSortArray) {
int firstList = 0;
int secondList = 0;
int nextArray = 0;
while (firstList < first.length && secondList < second.length) {
if (first[firstList] < second[secondList]) {
mergeSortArray[nextArray] = first[firstList];
firstList += 1;
} else {
mergeSortArray[nextArray] = second[secondList];
secondList += 1;
}
nextArray += 1;
}
while (firstList < first.length) {
mergeSortArray[nextArray] = first[firstList];
firstList += 1;
nextArray += 1;
}
while (secondList < second.length) {
mergeSortArray[nextArray] = second[secondList];
secondList += 1;
nextArray += 1;
}
}
}
Bubble.Sort:
public class BubbleSort extends Sorting{
public BubbleSort() {
super("Bubble Sort");
}
public static int[] sort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
}
Explanation / Answer
Hello there ,
Let me explain you .
1.TestSorting.java is the main Driver program of the application .
This whole application compares the time taken by various diff sort algorithm like merge sort,bubble sort and qucik sort with diff size of array .
int[] size = { 10, 50, 100, 500, 1000 };
createRandomArray() will create array of random numbes of the above sizes.
is the array of various sizes fo array on which we'll run our sortings.
2.StopWatch is the program to calculate time taken by the sort method.
It calculates the diff between start and end time of the execution .So that we can have total time taken by the specific sort method.
3. Sorting.java is the super class for all 3 sort classes. It mainly contains the sort method name whether it is "Merge"/"Quick"/"Bubble" sort .
4.QuickSort.java is the implementaion of the quick sort algorithm.
For learning all types of algorithm you should first get the knowledge of how diff sorting algortihms work.
5.Same way MergeSort.java is the implementation of merge sort algorithm.
6.Same way BubbleSort.java is the implmentation of buble sort algorithm .
You can try diff algorthm by chaging below line and can mesure the time taken by diff algos.
QuickSort.sort(a); by Mergesor.sort(a) etc.
Let me know if you still have doubts.
Thank you.