All Sorts Checkpoint
A place to visit if any sorting algorithm (in Java) is needed for quick use.
Sorts
The parent below will be inherited in objects for each of the following sorts:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
// interface that different sort type objects will be based on
public class Sort {
private String name;
public Sort() {
this.name = "None";
}
public String getName() {
return this.name;
}
public int[] sort(int[] arr) {
// to be overridden by the other methods
return arr;
}
public int[] sortWithSteps(int[] arr) {
// to be overwritten by the other methods
return arr;
}
public static String printArray(int[] arr) {
int n = arr.length;
String output = "[";
for (int i = 0; i < n; i++) {
output += arr[i];
if (i == n - 1) {
output += "]";
} else {
output += ", ";
}
}
return output;
}
}
Bubble Sort
Bubble sort is a type of sort that swaps adjacent larger values (at the lower index) with smaller values (at the higher index) until the array has been fully sorted.
public class BubbleSort extends Sort {
private String name;
// constructor with name
public BubbleSort() {
this.name = "Bubble Sort";
}
public String getName() {
return this.name;
}
// method for just a sort
public int[] sort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// swap arr[j+1] and arr[j], knowing that arr[j] is greater
swapped = true;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if (!swapped) {
break;
}
}
return arr;
}
// method that prints each step of the process
public int[] sortWithSteps(int[] arr) {
// introducing with initial array
System.out.println("We are starting the Bubble Sort process with the following array: \n\t" + Sort.printArray(arr));
// beginning the sort
System.out.println("We will now sort the array by swapping disorderly values that are right next to each other.");
boolean needsExample = true;
boolean swapped;
int passes = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swapping arr[j+1] and arr[j], knowing that arr[j] is greater
swapped = true;
if (needsExample) {
System.out.println("For example, because " + arr[j] + " is greater than the following value, " + arr[j + 1] + ", we will swap them.\n");
needsExample = false;
}
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if (!swapped) {
break;
}
passes++; // incrementing the number of passes that will be printed later
System.out.println("After " + passes + " pass" + (passes != 1 ? "es" : "") + ", the array looks like this: " + Sort.printArray(arr));
}
System.out.println("\nNow, look at the array! It has been fully sorted from least to greatest by swapping values with each pass.");
return arr;
}
public static void main(String[] args) {
int[] testArray = {54, 23, 53, 76, 34, 22, 59, 29};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.sortWithSteps(testArray);
}
}
BubbleSort.main(null);
We are starting the Bubble Sort process with the following array:
[54, 23, 53, 76, 34, 22, 59, 29]
We will now sort the array by swapping disorderly values that are right next to each other.
For example, because 54 is greater than the following value, 23, we will swap them.
After 1 pass, the array looks like this: [23, 53, 54, 34, 22, 59, 29, 76]
After 2 passes, the array looks like this: [23, 53, 34, 22, 54, 29, 59, 76]
After 3 passes, the array looks like this: [23, 34, 22, 53, 29, 54, 59, 76]
After 4 passes, the array looks like this: [23, 22, 34, 29, 53, 54, 59, 76]
After 5 passes, the array looks like this: [22, 23, 29, 34, 53, 54, 59, 76]
Now, look at the array! It has been fully sorted from least to greatest by swapping values with each pass.
Selection Sort
Here’s our sort: selection sort! It works by determining the minimum element in the unsorted portion of the array, swapping it to the earliest index of the unsorted section, and moving from there, with earliest section being the “sorted” section.
public class SelectionSort extends Sort {
private String name;
// constructor with name
public SelectionSort() {
this.name = "Selection Sort";
}
public String getName() {
return this.name;
}
public int[] sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minimumIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minimumIndex]) {
minimumIndex = j;
}
}
// swap the found minimum element with the earliest unsorted element
int temp = arr[minimumIndex];
arr[minimumIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
public int[] sortWithSteps(int[] arr) {
// introducing with initial array
System.out.println("We are starting the Selection Sort process with the following array: \n\t" + Sort.printArray(arr));
// beginning the sort
System.out.println("We will now sort the array by finding the minimum value and swapping it with the earliest element of the unsorted section.");
boolean needsExample = true;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minimumIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minimumIndex]) {
minimumIndex = j;
}
}
if (needsExample) {
// explanation for first swap
System.out.println("For example, because " + arr[minimumIndex] + " is the minimum value in the first pass, we will swap it with the earliest (unsorted) element: " + arr[0] + " at index 0.\n");
needsExample = false;
}
// swap the found minimum element with the earliest unsorted element
int temp = arr[minimumIndex];
arr[minimumIndex] = arr[i];
arr[i] = temp;
System.out.println("After " + (i + 1) + " pass" + ((i + 1) != 1 ? "es" : "") + ", the array looks like this: " + Sort.printArray(arr));
}
System.out.println("\nNow, look at the array! It has been fully sorted from least to greatest by bringing minimum values to the front with each pass.");
return arr;
}
public static void main(String[] args) {
int[] testArray = {54, 23, 53, 76, 34, 22, 59, 29};
SelectionSort selectionSort = new SelectionSort();
selectionSort.sortWithSteps(testArray);
}
}
SelectionSort.main(null);
We are starting the Selection Sort process with the following array:
[54, 23, 53, 76, 34, 22, 59, 29]
We will now sort the array by finding the minimum value and swapping it with the earliest element of the unsorted section.
For example, because 22 is the minimum value in the first pass, we will swap it with the earliest (unsorted) element: 54 at index 0.
After 1 pass, the array looks like this: [22, 23, 53, 76, 34, 54, 59, 29]
After 2 passes, the array looks like this: [22, 23, 53, 76, 34, 54, 59, 29]
After 3 passes, the array looks like this: [22, 23, 29, 76, 34, 54, 59, 53]
After 4 passes, the array looks like this: [22, 23, 29, 34, 76, 54, 59, 53]
After 5 passes, the array looks like this: [22, 23, 29, 34, 53, 54, 59, 76]
After 6 passes, the array looks like this: [22, 23, 29, 34, 53, 54, 59, 76]
After 7 passes, the array looks like this: [22, 23, 29, 34, 53, 54, 59, 76]
Now, look at the array! It has been fully sorted from least to greatest by bringing minimum values to the front with each pass.
Insertion Sort
This is a type of sort that works similar to selection in that values are analyzed for their specific position relative to those around them before being moved to a particular location, but instead of swapping to the front, values are compared to those at previous indexes and placed accordingly.
public class InsertionSort extends Sort {
private String name;
// constructor with name
public InsertionSort() {
this.name = "Insertion Sort";
}
public String getName() {
return this.name;
}
public int[] sort(int[] arr) {
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];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}
public int[] sortWithSteps(int[] arr) {
// introducing with initial array
System.out.println("We are starting the Insertion Sort process with the following array: \n\t" + Sort.printArray(arr));
// beginning the sort
System.out.println("We will now sort the array by comparing values (sequentially) with prior elements and placing in order accordingly.");
boolean needsExample = true;
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];
j = j - 1;
}
// example will be provided just over halfway through the sort
if ((arr.length / 2) == i && needsExample) {
System.out.println("\nNow that we are about halfway done sorting the array, let's look at the process of comparison for example.");
System.out.println("Right now, we are at index " + i + " with the value " + key + ".");
System.out.println("By iterating through previous values, we see that " + key + " should be put after " + arr[j] + " (which is at index " + j + ").");
System.out.println("Now, " + key + " will be in its proper place in the current sort: index " + (j + 1) + ".\n");
needsExample = false;
}
arr[j + 1] = key;
System.out.println("After " + (i + 1) + " pass" + ((i + 1) != 1 ? "es" : "") + ", the array looks like this: " + Sort.printArray(arr));
}
System.out.println("\nNow, look at the array! It has been fully sorted from least to greatest by comparing elements to those prior and placing them accordingly.");
return arr;
}
public static void main(String[] args) {
int[] testArray = {54, 23, 53, 76, 34, 22, 59, 29};
InsertionSort insertionSort = new InsertionSort();
insertionSort.sortWithSteps(testArray);
}
}
InsertionSort.main(null);
We are starting the Insertion Sort process with the following array:
[54, 23, 53, 76, 34, 22, 59, 29]
We will now sort the array by comparing values (sequentially) with prior elements and placing in order accordingly.
After 2 passes, the array looks like this: [23, 54, 53, 76, 34, 22, 59, 29]
After 3 passes, the array looks like this: [23, 53, 54, 76, 34, 22, 59, 29]
After 4 passes, the array looks like this: [23, 53, 54, 76, 34, 22, 59, 29]
Now that we are about halfway done sorting the array, let's look at the process of comparison for example.
Right now, we are at index 4 with the value 34.
By iterating through previous values, we see that 34 should be put after 23 (which is at index 0).
Now, 34 will be in its proper place in the current sort: index 1.
After 5 passes, the array looks like this: [23, 34, 53, 54, 76, 22, 59, 29]
After 6 passes, the array looks like this: [22, 23, 34, 53, 54, 76, 59, 29]
After 7 passes, the array looks like this: [22, 23, 34, 53, 54, 59, 76, 29]
After 8 passes, the array looks like this: [22, 23, 29, 34, 53, 54, 59, 76]
Now, look at the array! It has been fully sorted from least to greatest by comparing elements to those prior and placing them accordingly.
Merge Sort
This is the most complex type of sort compared to the others code-wise, but it basically divides an array in 2 until it cannot be divided further. It then sorts
public class MergeSort extends Sort {
private String name;
// constructor with name
public MergeSort() {
this.name = "Merge Sort";
}
public String getName() {
return this.name;
}
public int[] sort(int[] arr) {
mergeSort(arr, 0, arr.length - 1, false);
return arr;
}
public int[] sortWithSteps(int[] arr) {
// introducing with initial array
System.out.println("We are starting the Merge Sort process with the following array: \n\t" + Sort.printArray(arr));
// beginning/doing the sort
System.out.println("We will now sort the array by splitting the array into smaller subarrays and sorting them as they're merged back together.\n");
mergeSort(arr, 0, arr.length - 1, true);
// all done
System.out.println("\nNow, look at that final array! It has been fully sorted from least to greatest by sorting them after division and merging them.");
return arr;
}
private void mergeSort(int[] arr, int l, int r, boolean showSteps) {
if (l < r) {
// finding the middle point
int m = (l + r) / 2;
// sorting first and second halves (recursive, goes until finished)
mergeSort(arr, l, m, showSteps);
mergeSort(arr, m + 1, r, showSteps);
// merging the sorted halves
merge(arr, l, m, r, showSteps);
}
}
private void merge(int[] arr, int l, int m, int r, boolean showSteps) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
// copying data to temp arrays
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// merging the temp arrays
int i = 0, j = 0;
// initial index of merged subarray
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// copying remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// copying remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
// for detailed method
if (showSteps) {
System.out.print("Merged array: [");
for (int o = l; o <= r; o++) {
System.out.print(arr[o]);
if (o == r) {
System.out.println("]");
} else {
System.out.print(", ");
}
}
}
}
public static void main(String[] args) {
int[] testArray = {54, 23, 53, 76, 34, 22, 59, 29};
MergeSort mergeSort = new MergeSort();
mergeSort.sortWithSteps(testArray);
}
}
MergeSort.main(null);
We are starting the Merge Sort process with the following array:
[54, 23, 53, 76, 34, 22, 59, 29]
We will now sort the array by splitting the array into smaller subarrays and sorting them as they're merged back together.
Merged array: [23, 54]
Merged array: [53, 76]
Merged array: [23, 53, 54, 76]
Merged array: [22, 34]
Merged array: [29, 59]
Merged array: [22, 29, 34, 59]
Merged array: [22, 23, 29, 34, 53, 54, 59, 76]
Now, look at that final array! It has been fully sorted from least to greatest by sorting them after division and merging them.
Quick Sort
I’m not familiar with quick sort, so I spent extra time with this one. It also uses divide and conquer, but instead focuses on sorting values around a certain pivot value (above if greater and below if less than).
public class QuickSort extends Sort {
private String name;
// constructor with name
public QuickSort() {
this.name = "Quick Sort";
}
public String getName() {
return this.name;
}
public int[] sort(int[] arr) {
quickSort(arr, 0, arr.length - 1, false);
return arr;
}
public int[] sortWithSteps(int[] arr) {
// introducing with initial array
System.out.println("We are starting the Quick Sort process with the following array: \n\t" + Sort.printArray(arr));
// beginning/doing the sort
System.out.println("We will now sort the array by splitting the array up and sorting around a pivot value each time.\n");
System.out.println("To help visualize the values being swapped, all swaps made by the algorithm's process are shown below:");
quickSort(arr, 0, arr.length - 1, true);
// all done
System.out.println("FINAL ARRAY: " + Sort.printArray(arr));
System.out.println("\nNow, look at that array! It has been fully sorted from least to greatest by swapping values within the scope of a certain partition (divided and conquered).");
return arr;
}
private void quickSort(int[] arr, int low, int high, boolean showSteps) {
if (low < high) {
// pi is partitioning index, arr[pi] is at right place
int pi = partition(arr, low, high, showSteps);
// recursively sorting elements partition and after partition
quickSort(arr, low, pi - 1, showSteps);
quickSort(arr, pi + 1, high, showSteps);
}
}
private int partition(int[] arr, int low, int high, boolean showSteps) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// if the current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
// swapping arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
if (showSteps && arr[i] != arr[j]) {
System.out.println("SWAP - Pivot: " + pivot + ", arr[i]: " + arr[i] + ", arr[j]: " + arr[j] + ", Array: " + Sort.printArray(arr));
}
}
}
// swapping arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
if (showSteps && arr[i + 1] != arr[high]) {
System.out.println("SWAP - Pivot: " + pivot + ", arr[i + 1]: " + arr[i + 1] + ", arr[high]: " + arr[high] + ", Array: " + Sort.printArray(arr));
}
return i + 1;
}
public static void main(String[] args) {
int[] testArray = {54, 23, 53, 76, 34, 22, 59, 29};
QuickSort quickSort = new QuickSort();
quickSort.sortWithSteps(testArray);
}
}
QuickSort.main(null);
We are starting the Quick Sort process with the following array:
[54, 23, 53, 76, 34, 22, 59, 29]
We will now sort the array by splitting the array up and sorting around a pivot value each time.
To help visualize the values being swapped, all swaps made by the algorithm's process are shown below:
SWAP - Pivot: 29, arr[i]: 23, arr[j]: 54, Array: [23, 54, 53, 76, 34, 22, 59, 29]
SWAP - Pivot: 29, arr[i]: 22, arr[j]: 54, Array: [23, 22, 53, 76, 34, 54, 59, 29]
SWAP - Pivot: 29, arr[i + 1]: 29, arr[high]: 53, Array: [23, 22, 29, 76, 34, 54, 59, 53]
SWAP - Pivot: 22, arr[i + 1]: 22, arr[high]: 23, Array: [22, 23, 29, 76, 34, 54, 59, 53]
SWAP - Pivot: 53, arr[i]: 34, arr[j]: 76, Array: [22, 23, 29, 34, 76, 54, 59, 53]
SWAP - Pivot: 53, arr[i + 1]: 53, arr[high]: 76, Array: [22, 23, 29, 34, 53, 54, 59, 76]
FINAL ARRAY: [22, 23, 29, 34, 53, 54, 59, 76]
Now, look at that array! It has been fully sorted from least to greatest by swapping values within the scope of a certain partition (divided and conquered).
All Sorting Algorithms
Here’s a class that incorporates all of the sorting algorithms and allows the user to select which one to use.
public class SortingAlgorithm {
// used for sort calls
private Sort sortType;
public SortingAlgorithm() {
this.sortType = new BubbleSort(); // placeholder parent sort type
}
// getter method
public Sort getSortType() {
return this.sortType;
}
// used to set more specific subclass
public void setSortType(Sort sortType) {
this.sortType = sortType;
}
// // calls the sort itself
// public int[] sort(int[] arr) {
// return this.sortType.sort(arr);
// }
// // calls the sort itself, this time with steps
// public int[] sortWithSteps(int[] arr) {
// return this.sortType.sortWithSteps(arr);
// }
// used to input the initial array
public static int[] getInputArray() {
ArrayList<Integer> list = new ArrayList<>();
Scanner scanner = new Scanner(System.in); // for user input
System.out.println("Enter integers (type 'done' or nothing to finish):");
while (true) {
String input = scanner.nextLine();
if (input.equals("done") || input.equals("")) {
scanner.close();
break;
}
try {
int num = Integer.parseInt(input);
list.add(num);
} catch (NumberFormatException e) {
System.out.println("Invalid input! Please enter a valid integer or 'done'/nothing to finish.");
}
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
public static void main(String[] args) {
// used to change sort types
Sort[] sortTypes = {new BubbleSort(), new SelectionSort(), new InsertionSort(), new MergeSort(), new QuickSort()};
// object for access
SortingAlgorithm sortingAlgorithm = new SortingAlgorithm();
// starting with user input
System.out.println("Start by creating the array of numbers you'd like to sort!");
int[] sortArray = getInputArray();
// beginning menu of options
Scanner scanner = new Scanner(System.in); // for user input
while (true) {
System.out.println("What would you like to do? (Current Sort Type: " + sortingAlgorithm.getSortType().getName() + ")");
System.out.println("\t1. Modify Sort Type\n\t2. Perform Sort\n\t3. Modify Array\n\t4. Quit");
String input = scanner.nextLine();
if (input.equals("1")) { // modifying sort types
// displaying available sort types to the user
System.out.println("Available sorting algorithms:");
for (int i = 0; i < sortTypes.length; i++) {
System.out.println("\t" + (i+1) + ". " + sortTypes[i].getName());
}
// Prompt user for input
System.out.println("Enter the number corresponding to the sorting algorithm you want to use:");
try {
int index = Integer.parseInt(scanner.nextLine()) - 1; // subtracting 1 to convert user input to 0-based index
if (index >= 0 && index < sortTypes.length) {
// setting the selected sorting algorithm
sortingAlgorithm.setSortType(sortTypes[index]);
System.out.println("Sorting algorithm set to: " + sortTypes[index].getName());
} else {
System.out.println("Invalid input! Please enter a valid index.");
}
} catch (NumberFormatException e) {
System.out.println("Invalid input! Please enter a valid index.");
}
} else if (input.equals("2")) { // performing the sort
System.out.println("How would you like to sort the array?\n\t1. With Steps\n\t2. Without Steps");
String withSteps = scanner.nextLine();
if (withSteps.equals("1")) {
System.out.println();
int[] sortedArray = sortingAlgorithm.getSortType().sortWithSteps(sortArray);
System.out.println();
} else {
int[] sortedArray = sortingAlgorithm.getSortType().sort(sortArray);
System.out.println("\nFinal Array: " + Sort.printArray(sortedArray) + "\n");
}
} else if (input.equals("3")) { // modifying the array
sortArray = getInputArray();
} else if (input.equals("4")) { // quit
break;
} else {
System.out.println("Invalid input! Please enter a number between 1 and 4.");
}
}
scanner.close();
}
}
SortingAlgorithm.main(null);
Start by creating the array of numbers you'd like to sort!
Enter integers (type 'done' or nothing to finish):
What would you like to do? (Current Sort Type: Bubble Sort)
1. Modify Sort Type
2. Perform Sort
3. Modify Array
4. Quit
Available sorting algorithms:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Enter the number corresponding to the sorting algorithm you want to use:
Sorting algorithm set to: Selection Sort
What would you like to do? (Current Sort Type: Selection Sort)
1. Modify Sort Type
2. Perform Sort
3. Modify Array
4. Quit
How would you like to sort the array?
1. With Steps
2. Without Steps
We are starting the Selection Sort process with the following array:
[8, 2, 12, 19, 5, 3, 15, 14]
We will now sort the array by finding the minimum value and swapping it with the earliest element of the unsorted section.
For example, because 2 is the minimum value in the first pass, we will swap it with the earliest (unsorted) element: 8 at index 0.
After 1 pass, the array looks like this: [2, 8, 12, 19, 5, 3, 15, 14]
After 2 passes, the array looks like this: [2, 3, 12, 19, 5, 8, 15, 14]
After 3 passes, the array looks like this: [2, 3, 5, 19, 12, 8, 15, 14]
After 4 passes, the array looks like this: [2, 3, 5, 8, 12, 19, 15, 14]
After 5 passes, the array looks like this: [2, 3, 5, 8, 12, 19, 15, 14]
After 6 passes, the array looks like this: [2, 3, 5, 8, 12, 14, 15, 19]
After 7 passes, the array looks like this: [2, 3, 5, 8, 12, 14, 15, 19]
Now, look at the array! It has been fully sorted from least to greatest by bringing minimum values to the front with each pass.
What would you like to do? (Current Sort Type: Selection Sort)
1. Modify Sort Type
2. Perform Sort
3. Modify Array
4. Quit
Available sorting algorithms:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Enter the number corresponding to the sorting algorithm you want to use:
Sorting algorithm set to: Quick Sort
What would you like to do? (Current Sort Type: Quick Sort)
1. Modify Sort Type
2. Perform Sort
3. Modify Array
4. Quit
How would you like to sort the array?
1. With Steps
2. Without Steps
Final Array: [2, 3, 5, 8, 12, 14, 15, 19]
What would you like to do? (Current Sort Type: Quick Sort)
1. Modify Sort Type
2. Perform Sort
3. Modify Array
4. Quit