Selection Sort
Selection sorts separates a list into 2 parts (a sorted and unsorted part). It takes the smallest value in the unsorted list and swaps it with the first element in the sorted portion. This continues until the sorted portion is completely sorted and the unsorted portion is empty.
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;
}
}
}
Insertion Sort
Insertion sort is a simple comparison-based builds the final sorted array one element at a time. It iterates through the list, shifting each element to its correct position relative to the already sorted portion of the array.
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;
}
}
}
Merge Sort
Merge sort is a divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce a single sorted array.
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
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++;
}
}
}
Quick Sort
Quick sort is a divide-and-conquer sorting algorithm that works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public 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;
}
}
Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated for each pair of adjacent elements until the entire list is sorted.
public class BubbleSort {
public static void bubbleSort(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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
}
LinkedList Implementation
- My class adds a new node with the given data to the end of the list. If the list is empty (head == null), the new node becomes the head.
- Otherwise, it traverses to the end of the list and appends the new node there.
selectionSort() Method:
- Implements the selection sort algorithm to sort the list in ascending order.
- Starts from the head and iterates through each node.
- For each node, it finds the minimum node in the remaining unsorted part of the list.
- Swaps the data of the current node with the minimum node found.
public class Node {
String stringData;
int intData;
Node next;
public Node(String stringData, int intData) {
this.stringData = stringData;
this.intData = intData;
this.next = null;
}
}
public class LinkedList {
Node head;
public void append(String stringData, int intData) {
Node newNode = new Node(stringData, intData);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.stringData + ":" + current.intData + " -> ");
current = current.next;
}
System.out.println("null");
}
public void selectionSort() {
if (head == null || head.next == null) {
return;
}
Node current = head;
while (current != null) {
Node minNode = current;
Node temp = current.next;
while (temp != null) {
if (temp.intData < minNode.intData) {
minNode = temp;
}
temp = temp.next;
}
// Swap data
String tempStringData = current.stringData;
int tempIntData = current.intData;
current.stringData = minNode.stringData;
current.intData = minNode.intData;
minNode.stringData = tempStringData;
minNode.intData = tempIntData;
current = current.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append("Where", 64);
list.append("Am", 25);
list.append("I", 12);
list.append("What", 11);
list.append("Am", 19);
list.append("I", 100);
list.append("Doing", 23);
System.out.println("Original list:");
list.printList();
list.selectionSort();
System.out.println("Sorted list:");
list.printList();
}
}
LinkedList.main(null);
Original list:
Where:64 -> Am:25 -> I:12 -> What:11 -> Am:19 -> I:100 -> Doing:23 -> null
Sorted list:
What:11 -> I:12 -> Am:19 -> Doing:23 -> Am:25 -> Where:64 -> I:100 -> null
Making the Comparable Class
I made a class that extends Comparable in order to compare a bunch of fancy food items by price, as I think fancy food is overrated. Each object from this class would contain a name, a price, and a list of ingredients.
interface Collectable<T> extends Comparable<T> {
@Override
int compareTo(T other);
String toString();
}
class FancyFood implements Collectable<FancyFood> {
private String name;
private double price;
private String[] ingredients;
public FancyFood(String name, double price, String[] ingredients) {
this.name = name;
this.price = price;
this.ingredients = ingredients;
}
public String getName() { return name; }
public double getPrice() { return price; }
public String[] getIngredients() { return ingredients; }
@Override
public int compareTo(FancyFood other) {
return Double.compare(this.price, other.price);
}
@Override
public String toString() {
return name + " ($" + price + ")";
}
}
Testing
I repurposed the selectionsort algorithm for this form of linkedlist and sorted each of the fancy foods by price, while I didn’t print the list of ingredients I did sort by price and name. In the future it would be interesting to see if I could implenent a sort by alphabetical order or something more than just integer.
public class LinkedList {
Node head;
public void append(FancyFood data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public long selectionSort() {
long startTime = System.currentTimeMillis();
if (head == null || head.next == null) {
return 0;
}
Node current = head;
while (current != null) {
Node minNode = current;
Node temp = current.next;
while (temp != null) {
if (temp.data.compareTo(minNode.data) < 0) {
minNode = temp;
}
temp = temp.next;
}
FancyFood tempData = current.data;
current.data = minNode.data;
minNode.data = tempData;
current = current.next;
}
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
public long mergeSort() {
long startTime = System.currentTimeMillis();
head = mergeSort(head);
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
private Node mergeSort(Node node) {
if (node == null || node.next == null) {
return node;
}
Node middle = getMiddle(node);
Node nextOfMiddle = middle.next;
middle.next = null;
Node left = mergeSort(node);
Node right = mergeSort(nextOfMiddle);
return merge(left, right);
}
private Node merge(Node left, Node right) {
Node result = null;
if (left == null) {
return right;
}
if (right == null) {
return left;
}
if (left.data.compareTo(right.data) <= 0) {
result = left;
result.next = merge(left.next, right);
} else {
result = right;
result.next = merge(left, right.next);
}
return result;
}
private Node getMiddle(Node node) {
if (node == null) {
return node;
}
Node slow = node;
Node fast = node;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public long insertionSort() {
long startTime = System.currentTimeMillis();
if (head == null || head.next == null) {
return 0;
}
Node current = head;
while (current != null) {
Node index = current.next;
while (index != null) {
if (current.data.compareTo(index.data) > 0) {
FancyFood temp = current.data;
current.data = index.data;
index.data = temp;
}
index = index.next;
}
current = current.next;
}
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
public long bubbleSort() {
long startTime = System.currentTimeMillis();
if (head == null || head.next == null) {
return 0;
}
boolean swapped;
Node end = null;
do {
swapped = false;
Node current = head;
while (current.next != end) {
if (current.data.compareTo(current.next.data) > 0) {
FancyFood temp = current.data;
current.data = current.next.data;
current.next.data = temp;
swapped = true;
}
current = current.next;
}
end = current;
} while (swapped);
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
public long quickSort() {
long startTime = System.currentTimeMillis();
head = quickSort(head, getTail(head));
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
private Node quickSort(Node start, Node end) {
if (start == null || start == end) {
return start;
}
Node[] pivotNodes = partition(start, end);
Node leftStart = pivotNodes[0];
Node leftEnd = pivotNodes[1];
Node pivot = pivotNodes[2];
Node rightStart = pivotNodes[3];
Node rightEnd = pivotNodes[4];
if (leftStart != pivot) {
Node temp = leftStart;
while (temp.next != pivot) {
temp = temp.next;
}
temp.next = null;
leftStart = quickSort(leftStart, temp);
temp = getTail(leftStart);
temp.next = pivot;
}
pivot.next = quickSort(rightStart, rightEnd);
return (leftStart == pivot) ? leftStart : pivot;
}
private Node[] partition(Node start, Node end) {
Node pivot = end;
Node leftStart = null, leftEnd = null, rightStart = null, rightEnd = null, current = start;
while (current != end) {
if (current.data.compareTo(pivot.data) < 0) {
if (leftStart == null) {
leftStart = current;
leftEnd = current;
} else {
leftEnd.next = current;
leftEnd = current;
}
} else {
if (rightStart == null) {
rightStart = current;
rightEnd = current;
} else {
rightEnd.next = current;
rightEnd = current;
}
}
current = current.next;
}
if (leftEnd != null) {
leftEnd.next = pivot;
}
if (rightEnd != null) {
rightEnd.next = null;
}
return new Node[]{leftStart != null ? leftStart : pivot, leftEnd != null ? leftEnd : pivot, pivot, rightStart, rightEnd};
}
private Node getTail(Node node) {
while (node != null && node.next != null) {
node = node.next;
}
return node;
}
private static class Node {
FancyFood data;
Node next;
Node(FancyFood data) {
this.data = data;
this.next = null;
}
}
public LinkedList copy() {
LinkedList copiedList = new LinkedList();
Node current = head;
while (current != null) {
copiedList.append(current.data);
current = current.next;
}
return copiedList;
}
}
public class Tester {
public static String[] generateIngredients() {
int numIngredients = (int) (Math.random() * 5) + 3; // Random number of ingredients between 3 and 7
String[] ingredients = new String[numIngredients];
for (int i = 0; i < numIngredients; i++) {
String ingredient = "Ingredient" + i;
ingredients[i] = ingredient;
}
return ingredients;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
for (int i = 1; i <= 1000; i++) {
String name = "FancyFood" + i;
double price = Math.random() * 100 + 50; // Random price between 50 and 150
String[] ingredients = generateIngredients();
list.append(new FancyFood(name, price, ingredients));
}
System.out.println("Original list:");
// list.printList();
LinkedList copiedList1 = list.copy();
System.out.println("\nSorted list with Selection (Time taken: " + copiedList1.selectionSort() + " ms)");
// copiedList1.printList();
LinkedList copiedList2 = list.copy();
System.out.println("\nSorted list with Merge Sort (Time taken: " + copiedList2.mergeSort() + " ms)");
// copiedList2.printList();
LinkedList copiedList3 = list.copy();
System.out.println("\nSorted list with Insertion Sort (Time taken: " + copiedList3.insertionSort() + " ms)");
// copiedList3.printList();
LinkedList copiedList4 = list.copy();
System.out.println("\nSorted list with Quick Sort (Time taken: " + copiedList4.quickSort() + " ms)");
// copiedList4.printList();
LinkedList copiedList5 = list.copy();
System.out.println("\nSorted list with Bubble Sort (Time taken: " + copiedList5.bubbleSort() + " ms)");
// copiedList5.printList();
}
}
Tester.main(null);
Original list:
Sorted list with Selection (Time taken: 3 ms)
Sorted list with Merge Sort (Time taken: 2 ms)
Sorted list with Insertion Sort (Time taken: 6 ms)
Sorted list with Quick Sort (Time taken: 1 ms)
Sorted list with Bubble Sort (Time taken: 16 ms)
Algorythmic Reflection
Overall, this was quite the experience. For a lot of us, it was very different than what we were used to, but we still gained a lot from it. Our understanding of sorting algorithms strengthened and our collaboration skills were put on full display in being able to not only coordinate times to meet for rehearsals, but giving each other directing notes for acting. Each individual put in effort too, as we all had our lines completely memorized (how many other teams did that?). We managed to get a 48/50 on our presentation, and I think we all enjoyed the process. We made sure that each person, no matter their theater experience was. I think I also got a lot more familiar with my sort, having not heard of selection sort prior to this class and not really looking into it that much.
Rehearsal Pictures: