Sorting Algorithms
Review on sorting algorithms
abstract class Sort {
abstract void sort(int[] list);
/*
* @param n: the size of the list
* @param k: the number of simulations run
*
*/
public double runSimulations(int n, int k) {
double sumTime = 0;
for (int i = 0; i < k; i++) {
int[] list = new int[n];
for (int j = 0; j < n; j++) {
list[j] = (int) (Math.random() * 200);
}
double startTime = System.nanoTime();
sort(list);
double endTime = System.nanoTime();
sumTime += endTime - startTime;
}
return (sumTime / k) / 1000000;
}
}
class BubbleSort<T> extends Sort {
private double timeElapsed;
private int[] list;
BubbleSort(int[] list) {
this.list = list;
}
@Override
public void sort(int[] list) {
boolean unsorted = true;
while (unsorted) {
unsorted = false;
for (int i = 0; i < list.length - 1; i++) {
if (list[i] > list[i + 1]) {
int tmp = list[i];
list[i] = list[i + 1];
list[i + 1] = tmp;
unsorted = true;
}
}
}
this.list = list;
}
public void sort() {
sort(this.list);
}
public int[] get() {
return list;
}
}
class SelectionSort extends Sort {
private int[] list;
SelectionSort(int[] list) {
this.list = list;
}
public void sort() {
sort(this.list);
}
@Override
public void sort(int[] list) {
for (int i = 0; i < list.length - 1; i++) {
int smallest = list[i];
for (int j = i + 1; j < list.length; j++) {
if (smallest > list[j]) {
smallest = list[j];
}
if (list[i] != smallest) {
int tmp = list[i];
list[i] = smallest;
smallest = tmp;
}
}
}
this.list = list;
}
public int[] get() {
return list;
}
}
class InsertionSort extends Sort {
private int[] list;
InsertionSort(int[] list) {
this.list = list;
}
public void sort(int[] list) {
for (int i = 1; i < list.length; i++) {
int j = i;
// I'm gonna be honest I have no idea why it's j > 1 and not j > 0
while ((list[j - 1] > list[j]) && (j > 1)) {
int tmp = list[j - 1];
list[j - 1] = list[j];
list[j] = tmp;
j--;
}
}
this.list = list;
}
public void sort() {
sort(this.list);
}
public int[] get() {
return list;
}
}
class MergeSort extends Sort {
private int[] list;
MergeSort(int[] list) {
this.list = list;
}
public void sort() {
sort(this.list);
}
@Override
public void sort(int[] list) {
this.list = mergeSort(list);
}
public int[] mergeSort(int[] list) {
if (list.length == 1) {
return list;
}
int[] left = Arrays.copyOfRange(list, 0, (int) Math.floor(list.length/2.0));
int[] right = Arrays.copyOfRange(list, (int) Math.floor(list.length/2.0), list.length);
return merge(mergeSort(left), mergeSort(right));
}
public int[] merge(int[] arr1, int[] arr2) {
int[] merged = new int[arr1.length + arr2.length];
int counter = 0;
int ind1 = 0;
int ind2 = 0;
int size1 = arr1.length;
int size2 = arr2.length;
while (size1 != 0 || size2 != 0) {
if (size1 == 0) {
merged[counter] = arr2[ind2];
counter++;
ind2++;
size2--;
} else if (size2 == 0) {
merged[counter] = arr1[ind1];
counter++;
ind1++;
size1--;
} else if (arr1[ind1] <= arr2[ind2]) {
merged[counter] = arr1[ind1];
counter++;
ind1++;
size1--;
} else {
merged[counter] = arr2[ind2];
counter++;
ind2++;
size2--;
}
}
return merged;
}
public int[] get() {
return list;
}
}
public class SortTest {
public static void main(String[] args) {
int[] testArray = {3, 6, 1, 4, 3, 9, 8, 5, 6, 2};
System.out.println("=====================================");
System.out.println("Unsorted Array Example");
for (int num : testArray) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("=====================================");
BubbleSort bubbleTest = new BubbleSort(testArray);
bubbleTest.sort();
int[] sortedBubble = bubbleTest.get();
System.out.println("Bubble Sort Example");
for (int num : sortedBubble) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("Average of 12 simulations with 5000 elements: ");
System.out.println(bubbleTest.runSimulations(5000, 12) + " milliseconds");
System.out.println("Big O Notation: O(n^2)");
System.out.println("=====================================");
SelectionSort selectionTest = new SelectionSort(testArray);
selectionTest.sort();
int[] sortedSelection = selectionTest.get();
System.out.println("Selection Sort");
for (int num : sortedSelection) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("Average of 12 simulations with 5000 elements: ");
System.out.println(selectionTest.runSimulations(5000, 12) + " milliseconds");
System.out.println("Big O Notation: O(n^2)");
System.out.println("=====================================");
InsertionSort insertionTest = new InsertionSort(testArray);
insertionTest.sort();
int[] sortedInsertion = insertionTest.get();
System.out.println("Insertion Sort");
for (int num : sortedInsertion) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("Average of 12 simulations with 5000 elements: ");
System.out.println(insertionTest.runSimulations(5000, 12) + " milliseconds");
System.out.println("Big O Notation: O(n^2)");
System.out.println("=====================================");
MergeSort mergeTest = new MergeSort(testArray);
mergeTest.sort();
int[] sortedMerge = mergeTest.get();
System.out.println("Merge Sort");
for (int num : sortedMerge) {
System.out.print(num + " ");
}
System.out.println();
System.out.println("Average of 12 simulations with 5000 elements: ");
System.out.println(mergeTest.runSimulations(5000, 12) + " milliseconds");
System.out.println("Big O Notation: O(nlogn)");
System.out.println("=====================================");
}
}
SortTest.main(null);