Selection Sort
Functions by finding the minimum of an array then placing it at the beginning, repeating this excluding the placed elements.
public class Sort {
public static double[] selection(double[] arr) {
int len = arr.length;
for (int i = 0; i < len; i ++) {
double min = arr[i];
for (int j = i; j < len; j ++) {
if (arr[j] < min) {
arr[i] = arr[j];
arr[j] = min;
}
}
}
return arr;
}
public static String stringifyArr(double[] arr) {
String output = "[";
for (int i = 0; i < arr.length - 1; i ++) {
output += arr[i] + ", ";
}
output += arr[arr.length - 1] + "]";
return output;
}
public static void main(String[] args) {
double[] unsorted = {1.32, 654, 23, 543, 2, 4, 45254, 324, 25, 24, 234432};
System.out.println("Unsorted: " + Sort.stringifyArr(unsorted));
double[] sorted = Sort.selection(unsorted);
System.out.println("Sorted: " + Sort.stringifyArr(sorted));
}
}
Sort.main(null);
Unsorted: [1.32, 654.0, 23.0, 543.0, 2.0, 4.0, 45254.0, 324.0, 25.0, 24.0, 234432.0]
Sorted: [1.32, 24.0, 654.0, 654.0, 654.0, 654.0, 654.0, 45254.0, 45254.0, 45254.0, 234432.0]
Bubble Sort
Functions by swapping pairs of elements as necessary, passing through the array n-1 times.
public class Sort {
public static double[] bubble(double[] arr) {
double temp;
// n-1 passes
for (int i = arr.length - 1; i > 0; i --) {
for (int j = 0; j < i; j ++) {
// swap two elements if necessary
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
public static String stringifyArr(double[] arr) {
String output = "[";
for (int i = 0; i < arr.length - 1; i ++) {
output += arr[i] + ", ";
}
output += arr[arr.length - 1] + "]";
return output;
}
public static void main(String[] args) {
double[] unsorted = {1.32, 654, 23, 543, 2, 4, 45254, 324, 25, 24, 234432};
System.out.println("Unsorted: " + Sort.stringifyArr(unsorted));
double[] sorted = Sort.bubble(unsorted);
System.out.println("Sorted: " + Sort.stringifyArr(sorted));
}
}
Sort.main(null);
Unsorted: [1.32, 654.0, 23.0, 543.0, 2.0, 4.0, 45254.0, 324.0, 25.0, 24.0, 234432.0]
Sorted: [1.32, 2.0, 4.0, 23.0, 24.0, 25.0, 324.0, 543.0, 654.0, 45254.0, 234432.0]
Insertion Sort
Works by sectioning the array into an unsorted and sorted section, grabbing values from the unsorted section and placing them where appropriate.
// Decided to add a swap method at this point because it's more convenient and will be better later
public class Sort {
// Store array for sorting
double[] arr;
public Sort(double[] arr) {
this.arr = arr;
}
public void swap(int a, int b) {
double temp = arr[a];
arr[a] = arr[b];
arr[b] = arr[a];
}
public static double[] insertion(double[] arr) {
for (int i = 0; i < arr.length; i ++) {
double key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j --;
}
arr[j + 1] = key;
}
return arr;
}
public static String stringifyArr(double[] arr) {
String output = "[";
for (int i = 0; i < arr.length - 1; i ++) {
output += arr[i] + ", ";
}
output += arr[arr.length - 1] + "]";
return output;
}
public static void main(String[] args) {
double[] unsorted = {1.32, 654, 23, 543, 2, 4, 45254, 324, 25, 24, 234432};
System.out.println("Unsorted: " + Sort.stringifyArr(unsorted));
double[] sorted = Sort.insertion(unsorted);
System.out.println("Sorted: " + Sort.stringifyArr(sorted));
}
}
Sort.main(null);
Unsorted: [1.32, 654.0, 23.0, 543.0, 2.0, 4.0, 45254.0, 324.0, 25.0, 24.0, 234432.0]
Sorted: [1.32, 2.0, 4.0, 23.0, 24.0, 25.0, 324.0, 543.0, 654.0, 45254.0, 234432.0]
Merge Sort
Continuously divides an array into subarrays until each has n=1, then merges the arrays into a sorted order.
took this algorithm from geeks4geeks because I could not figure it out lol
// Decided to add a swap method at this point because it's more convenient and will be better later
public class Sort {
// Store array for sorting
double[] arr;
public Sort(double[] arr) {
this.arr = arr;
}
public void swap(int a, int b) {
double temp = arr[a];
arr[a] = arr[b];
arr[b] = arr[a];
}
public static void mergeRecur(double[] arr, int l, int m, int r) {
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
double L[] = new double[n1];
double R[] = new double[n2];
// Copy 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];
// Merge the temp arrays
// Initial indices of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
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++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void merge(double arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
merge(arr, l, m);
merge(arr, m + 1, r);
// Merge the sorted halves
mergeRecur(arr, l, m, r);
}
}
public static String stringifyArr(double[] arr) {
String output = "[";
for (int i = 0; i < arr.length - 1; i ++) {
output += arr[i] + ", ";
}
output += arr[arr.length - 1] + "]";
return output;
}
public static void main(String[] args) {
double[] unsorted = {1.32, 654, 23, 543, 2, 4, 45254, 324, 25, 24, 234432};
System.out.println("Unsorted: " + Sort.stringifyArr(unsorted));
Sort.merge(unsorted, 0, unsorted.length - 1);
double[] sorted = unsorted;
System.out.println("Sorted: " + Sort.stringifyArr(sorted));
}
}
Sort.main(null);
Unsorted: [1.32, 654.0, 23.0, 543.0, 2.0, 4.0, 45254.0, 324.0, 25.0, 24.0, 234432.0]
Sorted: [1.32, 2.0, 4.0, 23.0, 24.0, 25.0, 324.0, 543.0, 654.0, 45254.0, 234432.0]
Quick Sort
Sets a pivot point and creates partitions of the array, placing elements less than the pivot to the left of it, and greater elements to the right, within each partition, recursively.
// Decided to add a swap method at this point because it's more convenient and will be better later
public class Sort {
// A utility function to swap two elements
static void swap(double[] arr, int i, int j)
{
double temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(double[] arr, int low, int high)
{
// Choosing the pivot
double pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(double[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static String stringifyArr(double[] arr) {
String output = "[";
for (int i = 0; i < arr.length - 1; i ++) {
output += arr[i] + ", ";
}
output += arr[arr.length - 1] + "]";
return output;
}
public static void main(String[] args) {
double[] unsorted = {1.32, 654, 23, 543, 2, 4, 45254, 324, 25, 24, 234432};
System.out.println("Unsorted: " + Sort.stringifyArr(unsorted));
Sort.quickSort(unsorted, 0, unsorted.length - 1);
double[] sorted = unsorted;
System.out.println("Sorted: " + Sort.stringifyArr(sorted));
}
}
Sort.main(null);
Unsorted: [1.32, 654.0, 23.0, 543.0, 2.0, 4.0, 45254.0, 324.0, 25.0, 24.0, 234432.0]
Sorted: [1.32, 2.0, 4.0, 23.0, 24.0, 25.0, 324.0, 543.0, 654.0, 45254.0, 234432.0]
Main sorting thing
Combining basic sorts with Collectable object, basic T object, and LinkedList object
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type; // extender should define their data type
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// this method is used to compare toString of objects
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// static print method used by extended classes
public static void print(Collectable[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Collectable' properties
if (objs.length > 0) {
Collectable obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
// Generic "T" to represent any object that extends Collectable
public static <T extends Collectable> List<T> selectionSort(List<T> arr) {
int len = arr.size();
for (int i = 0; i < len; i ++) {
for (int j = i; j < len; j ++) {
// Collectable compareTo method
if (arr.get(i).compareTo(arr.get(j)) > 0) {
T temp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, temp);
}
}
}
return arr;
}
public static <T extends Collectable> List<T> bubbleSort(List<T> arr) {
// n-1 passes
for (int i = arr.size() - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
// Use compareTo method to compare Collectable objects
if (arr.get(j).compareTo(arr.get(j + 1)) > 0) {
T temp = arr.get(j);
arr.set(j, arr.get(j + 1));
arr.set(j + 1, temp);
}
}
}
return arr;
}
public static <T extends Collectable> List<T> insertionSort(List<T> arr) {
int len = arr.size();
for (int i = 1; i < len; i++) {
T key = arr.get(i);
int j = i - 1;
while (j >= 0 && arr.get(j).compareTo(key) > 0) {
arr.set(j + 1, arr.get(j));
j--;
}
arr.set(j + 1, key);
}
return arr;
}
public static <T extends Collectable> List<T> mergeSort(List<T> arr) {
if (arr.size() <= 1) {
return arr;
}
int mid = arr.size() / 2;
List<T> left = mergeSort(arr.subList(0, mid));
List<T> right = mergeSort(arr.subList(mid, arr.size()));
return merge(left, right);
}
private static <T extends Collectable> List<T> merge(List<T> left, List<T> right) {
List<T> merged = new LinkedList<>();
int leftIndex = 0, rightIndex = 0;
while (leftIndex < left.size() && rightIndex < right.size()) {
if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
merged.add(left.get(leftIndex++));
} else {
merged.add(right.get(rightIndex++));
}
}
merged.addAll(left.subList(leftIndex, left.size()));
merged.addAll(right.subList(rightIndex, right.size()));
return merged;
}
public static <T extends Collectable> void quickSort(List<T> arr) {
quickSort(arr, 0, arr.size() - 1);
}
private static <T extends Collectable> void quickSort(List<T> arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static <T extends Collectable> int partition(List<T> arr, int low, int high) {
T pivot = arr.get(high);
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr.get(j).compareTo(pivot) <= 0) {
i++;
Collections.swap(arr, i, j);
}
}
Collections.swap(arr, i + 1, high);
return i + 1;
}
}
public class Student extends Collectable {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Student.key = key;}
public enum KeyType implements KeyTypes {title, group, person, uid}
// Instance data
private final String group;
private final String person;
private final int uid;
Student(String group, String person, int uid) {
this.setType("Student");
this.group = group; // Group that the student is in
this.person = person; // Student Name
this.uid = uid; // Student ID
}
public static Student[] students() {
return new Student[] {
new Student("D", "Haoxuan Tong", 11),
new Student("A", "Toby Leeder", 3),
new Student("C", "Isabelle Gunawan", 8),
new Student("B", "AJ Ruiz", 5),
new Student("C", "Raymond Sheng", 7),
new Student("D", "Aaron Rubin", 12),
new Student("A", "Kevin Du", 2),
new Student("D", "Aiden Huynh", 13),
new Student("B", "Drew Reed", 6),
new Student("A", "Edwin Abraham", 1),
new Student("B", "Ishi Singh", 4),
new Student("C", "Ryan McWeeny", 9),
new Student("D", "Ekam Kaire", 10),
};
}
@Override
protected KeyTypes getKey() { return Student.key; }
@Override
public String toString() {
String output="";
if (KeyType.group.equals(this.getKey())) {
output += "Table Group: " + this.group;
} else if (KeyType.person.equals(this.getKey())) {
output += "Student Name: " + this.person;
} else if (KeyType.uid.equals(this.getKey())) {
output += "Student ID: " + this.uid;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.group + ", " + this.person + ", " + this.uid;
}
return output;
}
public static void main(String[] args)
{
Student[] objs = students();
// LinkedList is faster than ArrayList for insertion and deletion, but slower for randomization
// Each node is linked to either the next element (single link) or the next and previous (double linked)
List<Student> students = new LinkedList<Student>(Arrays.asList(objs));
Student.setOrder(KeyType.title);
Student.print(objs);
Student.setOrder(KeyType.group);
// Change algorithm here:
selectionSort(students);
// bubbleSort(students);
// insertionSort(students);
// mergeSort(students);
// quickSort(students);
for (Student student : students)
System.out.println(student);
}
}
Student.main(null);
class [LREPL.$JShell$17J$Student; 13
Collectable: Student listed by title
Student: D, Haoxuan Tong, 11
Student: A, Toby Leeder, 3
Student: C, Isabelle Gunawan, 8
Student: B, AJ Ruiz, 5
Student: C, Raymond Sheng, 7
Student: D, Aaron Rubin, 12
Student: A, Kevin Du, 2
Student: D, Aiden Huynh, 13
Student: B, Drew Reed, 6
Student: A, Edwin Abraham, 1
Student: B, Ishi Singh, 4
Student: C, Ryan McWeeny, 9
Student: D, Ekam Kaire, 10
Table Group: A
Table Group: A
Table Group: A
Table Group: B
Table Group: B
Table Group: B
Table Group: C
Table Group: C
Table Group: C
Table Group: D
Table Group: D
Table Group: D
Table Group: D
Reflection!! RAAAAH!!!!!
I was robbed. Mr. Mortensen, I was robbed. In broad daylight, too. Can you believe it? I certainly can’t. I just cannot. It was a blowout–we swept the competition with ease. And yet, what happened? What happened to us, Mr. Mortensen? We had our joy, our lives, our souls TAKEN from us. I will not stand for this.
My contributions to this event were writing the script with Drew and act act acting!
Anyways, that was a lot of fun. We want to do it again at night at the museum. Raah!