All Sort Review
This was a review of all sorts that were included in the Algorythmic performances. I used our previous project as a reference, so the classes include inheritance from a generic class.
A generic class for all sorts:
import java.util.Arrays;
import java.util.Random;
import com.google.gson.JsonObject;
public class Generics {
// instance variables to keep track of iterations, comparisons, and swaps
protected int iterations;
protected int comparisons;
protected int swaps;
public void sort(int[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
}
public String test() {
int arrayAmount = 0;
int arraySize = 5000;
long startTime = System.nanoTime();
for (int i = 0; i <= 12; i++) {
int[] arr = new int[arraySize];
Random rand = new Random();
for (int j = 0; j < arr.length; j++) {
arr[j] = rand.nextInt(1000);
}
sort(arr);
arrayAmount = i++;
}
long endTime = System.nanoTime();
System.out.println("Total arrays: " + arrayAmount);
System.out.println("Total array size per array: " + arraySize);
System.out.println("Total iterations: " + iterations);
System.out.println("Total comparisons: " + comparisons);
System.out.println("Total swaps: " + swaps);
System.out.println("Total time: " + (endTime - startTime) / 1000000 + " ms");
JsonObject analytics = new JsonObject();
analytics.addProperty("TotalArrays", arrayAmount);
analytics.addProperty("TotalArraySize", arraySize);
analytics.addProperty("TotalIterations", iterations);
analytics.addProperty("TotalComparisons", comparisons);
analytics.addProperty("TotalSwaps", swaps);
analytics.addProperty("TotalTime", (endTime - startTime) / 1000000 + " ms");
String analyticsString = analytics.toString();
System.out.println("Analytics: " + analyticsString);
return analyticsString;
}
public void testRandomValues() {
int[] arr = new int[10];
Random rand = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = rand.nextInt(1000);
}
System.out.println("Before sorting: " + Arrays.toString(arr));
sort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
The following sorts then inherit the generic class so that sorts and swaps can be tracked
public class Bubble extends Generics { //bubble class
@Override
public void sort(int[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
iterations++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swaps++;
comparisons++;
} else {
comparisons++;
}
}
}
}
public static void main(String[] args) {
Bubble bs = new Bubble();
bs.testRandomValues();
bs.test();
}
}
public class Insertion extends Generics { //insertion sort
@Override
public void sort(int[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Element changes position
j--;
iterations++;
comparisons++;
swaps++;
}
arr[j + 1] = key; // Element changes position
swaps++;
}
}
public static void main(String[] args) {
Insertion is = new Insertion();
is.testRandomValues();
is.test();
}
}
public class Merge extends Generics { //merge sort
@Override
public void sort(int[] arr) {
// reset instance variables
iterations = 0;
comparisons = 0;
swaps = 0;
mergeSort(arr, 0, arr.length - 1);
}
// recursive method for merge sort
private void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// middle point
int mid = left + (right - left) / 2;
// split both halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// merging sorted halves
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
rightArr[j] = arr[mid + 1 + j];
// merging arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
iterations++;
if (leftArr[i] <= rightArr[j]) {
// only increment swaps if there's an actual change in the value
if (arr[k] != leftArr[i]) {
swaps++;
}
arr[k] = leftArr[i];
i++;
} else {
if (arr[k] != rightArr[j]) {
swaps++;
}
arr[k] = rightArr[j];
j++;
}
k++;
comparisons++;
}
while (i < n1) {
if (arr[k] != leftArr[i]) {
swaps++;
}
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
if (arr[k] != rightArr[j]) {
swaps++;
}
arr[k] = rightArr[j];
j++;
k++;
}
}
public static void main(String[] args) {
Merge m = new Merge();
m.testRandomValues();
m.test();
}
}
public class Selection extends Generics {
@Override
public void sort(int[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
iterations++;
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
comparisons++;
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
swaps++;
}
}
public static void main(String[] args) {
Selection ss = new Selection();
ss.testRandomValues();
ss.test();
}
}
public class Quick extends Generics {
@Override
public void sort(int[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pt = partition(arr, low, high);
quickSort(arr, low, pt - 1);
quickSort(arr, pt + 1, high);
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
iterations++;
// if current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
swaps++;
}
comparisons++;
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
swaps++;
return i + 1;
}
public static void main(String[] args) {
Quick qs = new Quick();
qs.testRandomValues();
qs.test();
}
}
public class Main {
public static void main(String[] args) {
Bubble bs = new Bubble();
System.out.println("Bubble Sort:");
bs.testRandomValues();
bs.test();
Insertion is = new Insertion();
System.out.println("\nInsertion Sort:");
is.testRandomValues();
is.test();
Merge m = new Merge();
System.out.println("\nMerge Sort:");
m.testRandomValues();
m.test();
Selection ss = new Selection();
System.out.println("\nSelection Sort:");
ss.testRandomValues();
ss.test();
Quick qs = new Quick();
System.out.println("\nQuick Sort:");
qs.testRandomValues();
qs.test();
}
}
Main.main(null);
Bubble Sort:
Before sorting: [536, 138, 827, 717, 655, 588, 785, 374, 7, 505]
After sorting: [7, 138, 374, 505, 536, 588, 655, 717, 785, 827]
Total arrays: 12
Total array size per array: 5000
Total iterations: 12497500
Total comparisons: 12497500
Total swaps: 6203657
Total time: 143 ms
Analytics: {"TotalArrays":12,"TotalArraySize":5000,"TotalIterations":12497500,"TotalComparisons":12497500,"TotalSwaps":6203657,"TotalTime":"143 ms"}
Insertion Sort:
Before sorting: [176, 370, 490, 272, 734, 825, 128, 454, 855, 285]
After sorting: [128, 176, 272, 285, 370, 454, 490, 734, 825, 855]
Total arrays: 12
Total array size per array: 5000
Total iterations: 6332998
Total comparisons: 6332998
Total swaps: 6337997
Total time: 55 ms
Analytics: {"TotalArrays":12,"TotalArraySize":5000,"TotalIterations":6332998,"TotalComparisons":6332998,"TotalSwaps":6337997,"TotalTime":"55 ms"}
Merge Sort:
Before sorting: [810, 642, 799, 640, 959, 626, 135, 548, 502, 831]
After sorting: [135, 502, 548, 626, 640, 642, 799, 810, 831, 959]
Total arrays: 12
Total array size per array: 5000
Total iterations: 55214
Total comparisons: 55214
Total swaps: 55024
Total time: 5 ms
Analytics: {"TotalArrays":12,"TotalArraySize":5000,"TotalIterations":55214,"TotalComparisons":55214,"TotalSwaps":55024,"TotalTime":"5 ms"}
Selection Sort:
Before sorting: [148, 651, 130, 533, 689, 0, 961, 456, 93, 193]
After sorting: [0, 93, 130, 148, 193, 456, 533, 651, 689, 961]
Total arrays: 12
Total array size per array: 5000
Total iterations: 12497500
Total comparisons: 12497500
Total swaps: 4999
Total time: 121 ms
Analytics: {"TotalArrays":12,"TotalArraySize":5000,"TotalIterations":12497500,"TotalComparisons":12497500,"TotalSwaps":4999,"TotalTime":"121 ms"}
Quick Sort:
Before sorting: [917, 934, 221, 464, 253, 735, 928, 271, 675, 591]
After sorting: [221, 253, 271, 464, 591, 675, 735, 917, 928, 934]
Total arrays: 12
Total array size per array: 5000
Total iterations: 74185
Total comparisons: 74185
Total swaps: 34987
Total time: 5 ms
Analytics: {"TotalArrays":12,"TotalArraySize":5000,"TotalIterations":74185,"TotalComparisons":74185,"TotalSwaps":34987,"TotalTime":"5 ms"}
Trying out Linked Lists
Personal Team Review
Although we already worked with sorting algorithms many times, having people act it out on stage improved my understanding of it since they explained what they were doing step by step.
It was also just an overall fun experience. Not many classes let you do something outside of the classroom like this. Getting to cheer for everyone just improved my overall energy (despite having to be there at 8:00 on a Wednesday morning). I already love performances since I am a part of theater, but I could tell everyone else enjoyed it too based on how excited they were to be on stage. Everyone clearly put a lot of effort into their performances and it paid off.
As for our team, decided to make a short skit instead of doing a dance. We thought it would give us more freedom to make our performance entertaining, and everyone would get a chance to say something.
import java.util.Arrays;
// import comparable class
public abstract class Collectable implements Comparable<Collectable> {
public abstract String getType();
public abstract void setType(String type); // this is the key??
protected abstract KeyTypes getKey();
public interface KeyTypes {
String name();
}
public abstract String toString(); //build in toString method
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// not needed
// public static void print(Collectable[] objs) {
// System.out.println("Collectable objects:");
// for (Collectable obj : objs) {
// System.out.println(obj);
// }
// }
}
public class People extends Collectable { //extends custom Collectable class
public static KeyTypes key = KeyType.order;
public static void setOrder(KeyTypes key) { People.key = key; } // implementing the key
public enum KeyType implements KeyTypes { name, order }
private final String name;
private final int order;
People(String name, int order) {
this.setType("People");
this.name = name;
this.order = order;
}
@Override
protected KeyTypes getKey() {
return People.key;
}
@Override
public String toString() {
if (KeyType.name.equals(this.getKey())) {
return this.name;
} else if (KeyType.order.equals(this.getKey())) {
return String.valueOf(this.order);
} else {
return super.getType() + ": " + this.name + ", " + this.order;
}
}
public static People[] people() {
return new People[]{
new People("Aiden", 0),
new People("Ekam", 11),
new People("Edwin", 8),
new People("Bailey", 12),
new People("AJ", 4),
new People("Haoxuan", 5),
new People("Isabelle", 6),
new People("Aaron", 7),
new People("Katelyn", 9),
new People("Kevin", 2),
new People("Ryan", 10),
new People("Raymond", 1),
new People("Ishi", 3),
new People("Drew", 13),
};
}
public static void main(String[] args) {
People[] people = people();
Bubble bubbleSort = new Bubble();
System.out.println("Bubble Sort:");
bubbleSort.sort(people);
Collectable.print(people);
Insertion insertionSort = new Insertion();
System.out.println("Insertion Sort:");
insertionSort.sort(people);
Collectable.print(people);
Merge mergeSort = new Merge();
System.out.println("Merge Sort:");
mergeSort.sort(people);
Collectable.print(people);
Selection selectionSort = new Selection();
System.out.println("Selection Sort:");
selectionSort.sort(people);
Collectable.print(people);
}
}
public class Bubble extends Generics {
@Override
public void sort(Collectable[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
iterations++;
if (arr[j].compareTo(arr[j + 1]) > 0) { //compareTo
Collectable temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swaps++;
comparisons++;
} else {
comparisons++;
}
}
}
}
}
// same sort code as above
public class Insertion extends Generics {
@Override
public void sort(Collectable[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
int n = arr.length;
for (int i = 1; i < n; i++) {
Collectable key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].compareTo(key) > 0) { //compareTo
arr[j + 1] = arr[j];
j--;
iterations++;
comparisons++;
swaps++;
}
arr[j + 1] = key;
swaps++;
}
}
}
public class Merge extends Generics {
@Override
public void sort(Collectable[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
mergeSort(arr, 0, arr.length - 1);
}
private void mergeSort(Collectable[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private void merge(Collectable[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
Collectable[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
Collectable[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
iterations++;
if (leftArr[i].compareTo(rightArr[j]) <= 0) { // using compareTo
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
comparisons++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}
public class Selection extends Generics {
@Override
public void sort(Collectable[] arr) {
iterations = 0;
comparisons = 0;
swaps = 0;
selectionSort(arr, 0, arr.length - 1);
}
private void selectionSort(Collectable[] arr, int left, int right) {
if (left < right) {
int minIndex = left;
for (int i = left + 1; i <= right; i++) {
iterations++;
if (arr[i].compareTo(arr[minIndex]) < 0) { //compareT0
minIndex = i;
}
comparisons++;
}
swap(arr, minIndex, left);
swaps++;
selectionSort(arr, left + 1, right);
}
}
private void swap(Collectable[] arr, int i, int j) {
Collectable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Selection Sort:
Aiden, order: 0
Raymond, order: 1
Kevin, order: 2
Ishi, order: 3
AJ, order: 4
Haoxuan, order: 5
Isabelle, order: 6
Aaron, order: 7
Edwin, order: 8
Katelyn, order: 9
Ryan, order: 10
Ekam, order: 11
Bailey, order: 12
Drew, order: 13
swaps: 23