- Build into this Jupyter Notebook(s) for Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort. Share solutions.
- Build into this Jupyter Notebooks Tester methods that runs each Sort
- Commit to GitHub Repository often, try to use GitHub commits to show iterations on work
- Build your sorts into Generic T Queue using Collectables implementation to compare keys.
Selection Sort
Selection sort is a linear sort algorithm as it moves from index [0] to [n-1]. In the inner loop which is a second linear loop it compares two elements (like seen in the visual below) and notes which is smallest, after cycling to the end it swaps the smallest number to beginning position in the round.
// add selection sort code here
// have a tester method so it runs the sort
import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
selectionSort(arr);
System.out.println("Selection Sort: " + Arrays.toString(arr));
}
}
SelectionSort.main(null);
Selection Sort: [11, 12, 22, 25, 34, 64, 90]
Insertion Sort
Insertion sort is another linear algorithm that sorts elements from index [0] to index [n-1]. In the inner loop of this algorithm, it finds the gap, insertion point for the next item and inserts it. Each inner loop leave the list partially sorted according to outer loops index.
// add insertion sort code here
// have a tester method so it runs the sort
import java.util.Arrays;
public class InsertionSort {
public static void insertionSort(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;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
System.out.println("Insertion Sort: " + Arrays.toString(arr));
}
}
InsertionSort.main(null);
Insertion Sort: [11, 12, 22, 25, 34, 64, 90]
Merge Sort
This algorithm uses a divide and conquer algorithm, versus linear algorithm of insertion or selection sort. Looking at it can be complicated, but it is more simple than it looks. It divides the array into two different groups recursively, until it gets only two to compare, swaps if necessary. Then it pops out of the recursion, observe the cascading and then the inverted assembly in illustration, after pop it puts each split group back together using a sorted comparison.
// add merge sort code here
// have a tester method so it runs the sort
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
private static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
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];
int i = 0, j = 0;
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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Merge Sort: " + Arrays.toString(arr));
}
}
MergeSort.main(null);
Merge Sort: [11, 12, 22, 25, 34, 64, 90]
Quick Sort
QuickSort is a sorting algorithm that uses a divide-and-conquer strategy to sort an array. It does so by selecting a pivot element and then sorting values larger than it on one side and smaller to the other side, and then it repeats those steps until the array is sorted.
// add quick sort code here
// have a tester method so it runs the sort
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.length - 1);
System.out.println("Quick Sort: " + Arrays.toString(arr));
}
}
QuickSort.main(null)
Quick Sort: [11, 12, 22, 25, 34, 64, 90]
Bubble Sort
Bubble sort is a sorting algorithm that starts from the first element of an array and compares it with the second element. If the first element is greater than the second, we swap them. It continues this process until the end of the array, with the largest elements “bubbling” to the top.
// add bubble sort code here
// have a tester method so it runs the sort
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Bubble Sort: " + Arrays.toString(arr));
}
}
BubbleSort.main(null);
Bubble Sort: [11, 12, 22, 25, 34, 64, 90]