Inherited Sorting Test
In the process of the development of the mini-project Palette Puzzle.
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
public class SortingAlgorithm {
protected int swaps;
protected int comparisons;
protected long executionTime;
public SortingAlgorithm() {
this.swaps = 0;
this.comparisons = 0;
this.executionTime = 0;
}
public int getSwaps() {
return swaps;
}
public int getComparisons() {
return comparisons;
}
public long getExecutionTime() {
return executionTime;
}
public Integer[][] sort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
long startTime = System.nanoTime();
Integer[][] steps = performSort(colorValues, chosenColor);
long endTime = System.nanoTime();
executionTime = endTime - startTime;
return steps;
}
protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
// to be implemented by each sorting algorithm
return null;
}
protected void swap(Integer[] array, Integer i, Integer j) {
Integer temp = array[i];
array[i] = array[j];
array[j] = temp;
swaps++;
}
protected int compare(HashMap<Integer, Integer[]> colorValues, int i, int j, int chosenColor) {
comparisons++;
return Integer.compare(colorValues.get(i)[chosenColor], colorValues.get(j)[chosenColor]);
}
}
public class BubbleSort extends SortingAlgorithm {
@Override
protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
ArrayList<Integer[]> stepsList = new ArrayList<>();
// copying the original array indices to the first step
Integer[] initialIndices = new Integer[colorValues.size()];
for (int i = 0; i < colorValues.size(); i++) {
initialIndices[i] = i;
}
stepsList.add(Arrays.copyOf(initialIndices, initialIndices.length));
Integer[] indices = Arrays.copyOf(initialIndices, initialIndices.length);
// bubble sort
for (int i = 0; i < colorValues.size(); i++) {
boolean swapped = false; // flag to track whether any swaps were made in this pass
for (int j = 0; j < colorValues.size() - i - 1; j++) {
if (compare(colorValues, indices[j], indices[j + 1], chosenColor) > 0) {
swap(indices, j, j + 1);
swapped = true;
}
}
// if no swaps were made in this pass, the array is already sorted so we break out of the loop
if (!swapped) {
break;
}
// copying the current state of indices to the steps list
stepsList.add(Arrays.copyOf(indices, indices.length));
}
// converting the ArrayList to a 2D array
//Integer[][] steps = stepsList.toArray(new Integer[0][]);
return stepsList.toArray(new Integer[0][]);
}
public static void main(String[] args) {
BubbleSort bubbleSort = new BubbleSort();
Random random = new Random();
// testing
HashMap<Integer, Integer[]> colorValues = new HashMap<>();
// populating
Integer[] tempArray = {0, 0, 0};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
tempArray[j] = random.nextInt(256);
}
colorValues.put(i, tempArray.clone());
}
// sorting
Integer[][] steps = bubbleSort.sort(colorValues, 0);
// results
System.out.println("Steps (Passes):");
for (int i = 0; i < steps.length; i++) {
System.out.print("\t" + Arrays.toString(steps[i]));
if (i != steps.length - 1) {
System.out.println(",");
} else {
System.out.println();
}
}
Integer[] sortedIndexes = steps[steps.length - 1]; // this is the variable that will be sent from backend
// System.out.println("Sorted Array: " + Arrays.toString(steps[steps.length - 1]));
System.out.println("Sorted Colors (by red):"); // for testing
for (Integer index : sortedIndexes) {
System.out.println("\t" + index + ": " + Arrays.toString(colorValues.get(index)));
}
System.out.println("Swaps: " + bubbleSort.getSwaps());
System.out.println("Comparisons: " + bubbleSort.getComparisons());
System.out.println("Execution Time: " + bubbleSort.getExecutionTime() + " nanoseconds");
}
}
BubbleSort.main(null);
Steps (Passes):
[0, 1, 2, 3, 4, 5, 6, 7],
[1, 0, 2, 4, 5, 6, 7, 3],
[1, 0, 4, 2, 6, 7, 5, 3],
[1, 0, 4, 6, 7, 2, 5, 3]
Sorted Colors (by red):
1: [26, 48, 6]
0: [34, 206, 110]
4: [50, 122, 154]
6: [105, 101, 90]
7: [115, 171, 8]
2: [160, 239, 151]
5: [206, 238, 121]
3: [243, 181, 68]
Swaps: 10
Comparisons: 22
Execution Time: 67294 nanoseconds
public class InsertionSort extends SortingAlgorithm {
@Override
protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
ArrayList<Integer[]> stepsList = new ArrayList<>();
// copying the original array indices to the first step
Integer[] initialIndices = new Integer[colorValues.size()];
for (int i = 0; i < colorValues.size(); i++) {
initialIndices[i] = i;
}
stepsList.add(Arrays.copyOf(initialIndices, initialIndices.length));
Integer[] indices = Arrays.copyOf(initialIndices, initialIndices.length);
// insertion sort
for (int i = 1; i < colorValues.size(); i++) {
int key = indices[i];
int j = i - 1;
// moving elements of indices that are greater than key one position ahead of their current position
while (j >= 0 && compare(colorValues, indices[j], key, chosenColor) > 0) {
indices[j + 1] = indices[j];
j = j - 1;
swaps++;
}
indices[j + 1] = key;
// copying the current state of indices to the steps list
stepsList.add(Arrays.copyOf(indices, indices.length));
}
return stepsList.toArray(new Integer[0][]);
}
public static void main(String[] args) {
InsertionSort insertionSort = new InsertionSort();
Random random = new Random();
// testing
HashMap<Integer, Integer[]> colorValues = new HashMap<>();
// populating
Integer[] tempArray = {0, 0, 0};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
tempArray[j] = random.nextInt(256);
}
colorValues.put(i, tempArray.clone());
}
// sorting
Integer[][] steps = insertionSort.sort(colorValues, 0);
// results
System.out.println("Steps:");
for (int i = 0; i < steps.length; i++) {
System.out.print("\t" + Arrays.toString(steps[i]));
if (i != steps.length - 1) {
System.out.println(",");
} else {
System.out.println();
}
}
Integer[] sortedIndexes = steps[steps.length - 1]; // this is the variable that will be sent from backend
// System.out.println("Sorted Array: " + Arrays.toString(steps[steps.length - 1]));
System.out.println("Sorted Colors (by red):"); // for testing
for (Integer index : sortedIndexes) {
System.out.println("\t" + index + ": " + Arrays.toString(colorValues.get(index)));
}
System.out.println("Swaps (Insertions): " + insertionSort.getSwaps());
System.out.println("Comparisons: " + insertionSort.getComparisons());
System.out.println("Execution Time: " + insertionSort.getExecutionTime() + " nanoseconds");
}
}
InsertionSort.main(null);
Steps:
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 2, 1, 3, 4, 5, 6, 7],
[0, 2, 3, 1, 4, 5, 6, 7],
[0, 2, 3, 1, 4, 5, 6, 7],
[0, 2, 5, 3, 1, 4, 6, 7],
[0, 2, 5, 6, 3, 1, 4, 7],
[0, 2, 5, 6, 3, 7, 1, 4]
Sorted Colors (by red):
0: [14, 184, 60]
2: [19, 82, 93]
5: [37, 188, 120]
6: [44, 86, 40]
3: [61, 151, 6]
7: [68, 205, 70]
1: [134, 148, 61]
4: [183, 25, 230]
Swaps (Insertions): 10
Comparisons: 17
Execution Time: 58285 nanoseconds
public class SelectionSort extends SortingAlgorithm {
@Override
protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
ArrayList<Integer[]> stepsList = new ArrayList<>();
// copying the original array indices to the first step
Integer[] initialIndices = new Integer[colorValues.size()];
for (int i = 0; i < colorValues.size(); i++) {
initialIndices[i] = i;
}
stepsList.add(Arrays.copyOf(initialIndices, initialIndices.length));
Integer[] indices = Arrays.copyOf(initialIndices, initialIndices.length);
// selection sort
for (int i = 0; i < colorValues.size() - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < colorValues.size(); j++) {
if (compare(colorValues, indices[j], indices[minIndex], chosenColor) < 0) {
minIndex = j;
}
}
swap(indices, i, minIndex);
// copying the current state of indices to the steps list
stepsList.add(Arrays.copyOf(indices, indices.length));
}
// converting the ArrayList to a 2D array when returning, as all do
return stepsList.toArray(new Integer[0][]);
}
public static void main(String[] args) {
SelectionSort selectionSort = new SelectionSort();
Random random = new Random();
// testing
HashMap<Integer, Integer[]> colorValues = new HashMap<>();
// populating
Integer[] tempArray = {0, 0, 0};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
tempArray[j] = random.nextInt(256);
}
colorValues.put(i, tempArray.clone());
}
// sorting
Integer[][] steps = selectionSort.sort(colorValues, 0);
// results
System.out.println("Steps:");
for (int i = 0; i < steps.length; i++) {
System.out.print("\t" + Arrays.toString(steps[i]));
if (i != steps.length - 1) {
System.out.println(",");
} else {
System.out.println();
}
}
Integer[] sortedIndexes = steps[steps.length - 1]; // this is the variable that will be sent from backend
// System.out.println("Sorted Array: " + Arrays.toString(steps[steps.length - 1]));
System.out.println("Sorted Colors (by red):"); // for testing
for (Integer index : sortedIndexes) {
System.out.println("\t" + index + ": " + Arrays.toString(colorValues.get(index)));
}
System.out.println("Swaps: " + selectionSort.getSwaps());
System.out.println("Comparisons: " + selectionSort.getComparisons());
System.out.println("Execution Time: " + selectionSort.getExecutionTime() + " nanoseconds");
}
}
SelectionSort.main(null);
Steps:
[0, 1, 2, 3, 4, 5, 6, 7],
[4, 1, 2, 3, 0, 5, 6, 7],
[4, 2, 1, 3, 0, 5, 6, 7],
[4, 2, 6, 3, 0, 5, 1, 7],
[4, 2, 6, 0, 3, 5, 1, 7],
[4, 2, 6, 0, 1, 5, 3, 7],
[4, 2, 6, 0, 1, 3, 5, 7],
[4, 2, 6, 0, 1, 3, 5, 7]
Sorted Colors (by red):
4: [3, 35, 22]
2: [15, 30, 15]
6: [22, 239, 120]
0: [41, 3, 118]
1: [56, 50, 146]
3: [98, 165, 147]
5: [200, 222, 201]
7: [226, 133, 231]
Swaps: 7
Comparisons: 28
Execution Time: 55800 nanoseconds
public class MergeSort extends SortingAlgorithm {
@Override
protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
ArrayList<Integer[]> steps = new ArrayList<>();
Integer[] indexes = new Integer[colorValues.size()];
// initialize indexes array with sorted order
for (int i = 0; i < colorValues.size(); i++) {
indexes[i] = i;
}
mergeSort(indexes, colorValues, chosenColor, steps);
// convert ArrayList to 2D array to be returned
return steps.toArray(new Integer[0][]);
}
private void mergeSort(Integer[] array, HashMap<Integer, Integer[]> colorValues, Integer chosenColor, ArrayList<Integer[]> steps) {
if (array.length <= 1) {
return; // indicates that it's already sorted
}
// splitting the array into two halves
Integer mid = array.length / 2;
Integer[] leftArray = Arrays.copyOfRange(array, 0, mid);
Integer[] rightArray = Arrays.copyOfRange(array, mid, array.length);
// recursively sorting each half
mergeSort(leftArray, colorValues, chosenColor, steps);
mergeSort(rightArray, colorValues, chosenColor, steps);
// merging the sorted halves
merge(array, leftArray, rightArray, colorValues, chosenColor, steps);
}
private void merge(Integer[] array, Integer[] leftArray, Integer[] rightArray, HashMap<Integer, Integer[]> colorValues, Integer chosenColor, ArrayList<Integer[]> steps) {
int leftIndex = 0, rightIndex = 0, arrayIndex = 0;
while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
Integer leftKey = leftArray[leftIndex];
Integer rightKey = rightArray[rightIndex];
// comparing the chosen color channel values
Integer leftColorValue = colorValues.get(leftKey)[chosenColor];
Integer rightColorValue = colorValues.get(rightKey)[chosenColor];
comparisons++;
if (leftColorValue <= rightColorValue) {
array[arrayIndex++] = leftKey;
leftIndex++;
} else {
array[arrayIndex++] = rightKey;
rightIndex++;
}
}
// copying remaining elements from leftArray
while (leftIndex < leftArray.length) {
swaps++;
array[arrayIndex++] = leftArray[leftIndex++];
}
// copying remaining elements from rightArray
while (rightIndex < rightArray.length) {
swaps++;
array[arrayIndex++] = rightArray[rightIndex++];
}
// add current state of sort to steps
steps.add(Arrays.copyOf(array, array.length));
}
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
Random random = new Random();
// testing
HashMap<Integer, Integer[]> colorValues = new HashMap<>();
// populating
Integer[] tempArray = {0, 0, 0};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
tempArray[j] = random.nextInt(256);
}
colorValues.put(i, tempArray.clone());
}
// sorting
Integer[][] steps = mergeSort.sort(colorValues, 0);
// results
System.out.println("Steps:");
for (int i = 0; i < steps.length; i++) {
System.out.print("\t" + Arrays.toString(steps[i]));
if (i != steps.length - 1) {
System.out.println(",");
} else {
System.out.println();
}
}
Integer[] sortedIndexes = steps[steps.length - 1]; // this is the variable that will be sent from backend
// System.out.println("Sorted Array: " + Arrays.toString(steps[steps.length - 1]));
System.out.println("Sorted Colors (by red):"); // for testing
for (Integer index : sortedIndexes) {
System.out.println("\t" + index + ": " + Arrays.toString(colorValues.get(index)));
}
System.out.println("Swaps (Insertions): " + mergeSort.getSwaps());
System.out.println("Comparisons: " + mergeSort.getComparisons());
System.out.println("Execution Time: " + mergeSort.getExecutionTime() + " nanoseconds");
}
}
MergeSort.main(null);
Steps:
[1, 0],
[2, 3],
[1, 2, 0, 3],
[5, 4],
[6, 7],
[6, 5, 4, 7],
[1, 2, 0, 6, 5, 3, 4, 7]
Sorted Colors (by red):
1: [34, 61, 252]
2: [48, 21, 10]
0: [79, 167, 100]
6: [153, 138, 250]
5: [168, 117, 83]
3: [191, 72, 50]
4: [209, 163, 50]
7: [252, 131, 88]
Swaps (Insertions): 8
Comparisons: 16
Execution Time: 21769 nanoseconds
private void mergeSort(HashMap<Integer, Integer[]> colorValue, Integer[] indexArray, Integer chosenColor, ArrayList<Integer[]> steps) {
ArrayList<Integer[]> currentValues = new ArrayList<>();
for (int i = 0; i < indexArray.length; i += 2) {
if (i + 1 < indexArray.length) {
Integer[] pair = {indexArray[i], indexArray[i + 1]};
currentValues.add(pair);
}
}
// step with pairs
for (int j = 0; j < currentValues.size(); j++) {
comparisons++;
if (colorValue.get(currentValues.get(j)[0])[chosenColor] > colorValue.get(currentValues.get(j)[1])[chosenColor]) {
swap(ArrayList.get(j), 0, 1);
}
}
Integer[] currentStep = new Integer[indexArray.length];
for (int k = 0; k < currentValues.size(); k++) {
System.arraycopy(currentValues.get(k), 0, combinedArray, k * 2);
}
steps.add(currentStep)
// start sort with recombining
while (currentValues.size() > 1) {
}
}