The Event
My favorite performance, other than our own ofcourse, was Drew’s. His group did an interpretation of a murder mystery which was really fun and interactive. We recieved a perfect score which was great. We were praised for having legible numbers, humorous concept, and easy to understand process. Granted we did have an easier sort, but it was great to brainstorm and write the script regardless. Our team had alot of fun and learned about all the other sort types as well. Below I took notes, added code, and visuals to explain my understanding of the sorts for future reference.
Selection Sort
Repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element.
import java.util.ArrayList;
import java.util.List;
// Implementing the Comparable interface
public class SortableList<T extends Comparable<T>> {
private List<T> list;
// Here I initialize the list using a constructor
public SortableList() {
list = new ArrayList<>();
}
// Here I write a method to add an element to the list
public void add(T element) {
list.add(element);
}
// Here is a method to sort the list using selection sort
public void selectionSort() {
int n = list.size(); // size of the list
// traversal through all elements of the list
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // assuming current element is minimum
// finding index of the minimum element in the unsorted portion
for (int j = i + 1; j < n; j++) {
// compare current element with minIndex
// if current element < min , update minIndex
// using list.get here and compareTo
if (list.get(j).compareTo(list.get(minIndex)) < 0) {
minIndex = j;
}
}
// Swap the minimum element with the first unsorted element
T temp = list.get(minIndex);
list.set(minIndex, list.get(i));
list.set(i, temp);
}
}
// method to display the elements of the list
public void display() {
for (T element : list) {
System.out.print(element + " ");
}
System.out.println();
}
// tester method
public static void main(String[] args) {
SortableList<Integer> sortableList = new SortableList<>();
// Adding elements to the list
sortableList.add(5);
sortableList.add(2);
sortableList.add(7);
sortableList.add(1);
sortableList.add(9);
// Displaying the unsorted list
System.out.println("Unsorted List:");
sortableList.display();
// Sorting the list
sortableList.selectionSort();
// Displaying the sorted list
System.out.println("Sorted List:");
sortableList.display(); // .display
}
}
System.out.println("--SELECTION SORT--");
SortableList.main(null);
--SELECTION SORT--
Unsorted List:
5 2 7 1 9
Sorted List:
1 2 5 7 9
Insertion Sort
Builds the sorted array one element at a time by inserting each unsorted element into its correct position within the sorted portion.
import java.util.ArrayList;
import java.util.List;
// implement the Comparable interface
public class SortableList<T extends Comparable<T>> {
private List<T> list;
// constructo , initializing tlist
public SortableList() {
list = new ArrayList<>();
}
// method for adding an element to the list
public void add(T element) {
list.add(element); // .add()
}
// method to sort the list - insertion sort
public void insertionSort() {
int n = list.size(); // size of the list .size() method
// traverse through all elements starting from second one
for (int i = 1; i < n; i++) {
T key = list.get(i); // store the element to be inserted
int j = i - 1;
// Move elements of list[0..i-1], that are greater than first/key, to one position ahead of their current position
while (j >= 0 && list.get(j).compareTo(key) > 0) {
list.set(j + 1, list.get(j));
j = j - 1;
}
list.set(j + 1, key); // Insert the key at its correct position
}
}
// method to display the elements of the list
public void display() {
for (T element : list) {
System.out.print(element + " ");
}
System.out.println();
}
// Tester method
public static void main(String[] args) {
SortableList<Integer> sortableList = new SortableList<>();
// add elements to the list
sortableList.add(5);
sortableList.add(2);
sortableList.add(7);
sortableList.add(1);
sortableList.add(9);
// display the unsorted list
System.out.println("Unsorted List:");
sortableList.display();
// insertion sort
sortableList.insertionSort();
// display the sorted list
System.out.println("Sorted List:");
sortableList.display();
}
}
System.out.println("--INSERTION SORT--");
SortableList.main(null);
--INSERTION SORT--
Unsorted List:
5 2 7 1 9
Sorted List:
1 2 5 7 9
Merge Sort
Divides the array into halves, sorts the halves independently, and then merges them back together in a sorted manner.
import java.util.ArrayList;
import java.util.List;
// Comparable interface
public class SortableList<T extends Comparable<T>> {
private List<T> list;
// constructor to initialize t list
public SortableList() {
list = new ArrayList<>();
}
// method to add an element to the list
public void add(T element) {
list.add(element);
}
// Merge sort
public void mergeSort() {
mergeSortHelper(list, 0, list.size() - 1);
}
// helper method for merge sort
private void mergeSortHelper(List<T> arr, int left, int right) { // list, index of first element, index of last element
if (left < right) {
// find the middle point
int mid = (left + right) / 2;
// split first and second halves
mergeSortHelper(arr, left, mid);
mergeSortHelper(arr, mid + 1, right);
// merge the sorted halves
merge(arr, left, mid, right);
}
}
// merge two sorted sublists into one sorted list
private void merge(List<T> arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// temporary arrays
List<T> L = new ArrayList<>();
List<T> R = new ArrayList<>();
// comapre within temporary arrays
for (int i = 0; i < n1; ++i) {
L.add(arr.get(left + i));
}
for (int j = 0; j < n2; ++j) {
R.add(arr.get(mid + 1 + j));
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L.get(i).compareTo(R.get(j)) <= 0) {
arr.set(k, L.get(i));
i++;
} else {
arr.set(k, R.get(j));
j++;
}
k++;
}
// merge the temporary arrays back into arr[left..right]
while (i < n1) {
arr.set(k, L.get(i));
i++;
k++;
}
while (j < n2) {
arr.set(k, R.get(j));
j++;
k++;
}
}
// method to display the elements of the list
public void display() {
for (T element : list) {
System.out.print(element + " ");
}
System.out.println();
}
// Tester method
public static void main(String[] args) {
SortableList<Integer> sortableList = new SortableList<>();
// add elements to the list
sortableList.add(5);
sortableList.add(2);
sortableList.add(7);
sortableList.add(1);
sortableList.add(9);
// display the unsorted list
System.out.println("Unsorted List:");
sortableList.display();
// sort the list using merge sort
sortableList.mergeSort();
// display the sorted list
System.out.println("Sorted List:");
sortableList.display();
}
}
System.out.println("--MERGE SORT--");
SortableList.main(null);
--MERGE SORT--
Unsorted List:
5 2 7 1 9
Sorted List:
1 2 5 7 9
Bubble Sort
Repeatedly swaps adjacent elements if they are in the wrong order until the entire array is sorted.
import java.util.ArrayList;
import java.util.List;
// implement comparable
public class SortableList<T extends Comparable<T>> {
private List<T> list;
// constructor to initialize the list
public SortableList() {
list = new ArrayList<>();
}
// add an element to the list
public void add(T element) {
list.add(element);
}
// sort the list using bubble sort
public void bubbleSort() {
int n = list.size();
// Traverse through all elements
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
// Swap if the current element is greater than the next one
if (list.get(j).compareTo(list.get(j + 1)) > 0) {
T temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
// method to display the elements of the list
public void display() {
for (T element : list) {
System.out.print(element + " ");
}
System.out.println();
}
// tester method
public static void main(String[] args) {
SortableList<Integer> sortableList = new SortableList<>();
// Adding elements to the list
sortableList.add(5);
sortableList.add(2);
sortableList.add(7);
sortableList.add(1);
sortableList.add(9);
// Displaying the unsorted list
System.out.println("Unsorted List:");
sortableList.display();
// Sorting the list using bubble sort
sortableList.bubbleSort();
// Displaying the sorted list
System.out.println("Sorted List:");
sortableList.display();
}
}
System.out.println("--BUBBLE SORT--");
SortableList.main(null);
--BUBBLE SORT--
Unsorted List:
5 2 7 1 9
Sorted List:
1 2 5 7 9
Quick Sort
Divides the array into two sub-arrays based on a pivot element, sorts each sub-array, and then combines them.
import java.util.ArrayList;
import java.util.List;
// implement comparable
public class SortableList<T extends Comparable<T>> {
private List<T> list;
// contructor to initialize list
public SortableList() {
list = new ArrayList<>();
}
// method to add element to list
public void add(T element) {
list.add(element);
}
// method to sort - quick sort
public void quickSort() {
quickSortHelper(list, 0, list.size() - 1);
}
// helper method for quick sort
private void quickSortHelper(List<T> arr, int low, int high) {
if (low < high) {
// Partition the array, arr[p..q] is now at correct position
int partitionIndex = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSortHelper(arr, low, partitionIndex - 1);
quickSortHelper(arr, partitionIndex + 1, high);
}
}
// Partition the array into two sub-arrays
private int partition(List<T> arr, int low, int high) {
T pivot = arr.get(high); // Pivot element (last element)
int i = low - 1; // Index of smaller element
// traverse through all elements except the pivot
for (int j = low; j < high; j++) {
// if current element is smaller than or equal to the pivot
if (arr.get(j).compareTo(pivot) <= 0) {
i++;
// Swap arr[i] and arr[j]
T temp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, temp);
}
}
// swap arr[i+1] and arr[high] (or pivot)
T temp = arr.get(i + 1);
arr.set(i + 1, arr.get(high));
arr.set(high, temp);
return i + 1; // return the partition index
}
// display the elements of the list
public void display() {
for (T element : list) {
System.out.print(element + " ");
}
System.out.println();
}
// tester method
public static void main(String[] args) {
SortableList<Integer> sortableList = new SortableList<>();
// adding elements to the list
sortableList.add(5);
sortableList.add(2);
sortableList.add(7);
sortableList.add(1);
sortableList.add(9);
// displaying the unsorted list
System.out.println("Unsorted List:");
sortableList.display();
// sort the list using quick sort
sortableList.quickSort();
// display the sorted list
System.out.println("Sorted List:");
sortableList.display();
}
}
System.out.println("--QUICK SORT--");
SortableList.main(null);
--QUICK SORT--
Unsorted List:
5 2 7 1 9
Sorted List:
1 2 5 7 9
Custom implementation of a sortable list in Java
Using bubble sort. Creating a class , BubbleSortableList that extends ArrayList, and override the toString and compareTo methods
import java.util.ArrayList;
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person other) {
// Compare person objects by age
return Integer.compare(this.age, other.age);
}
@Override
public String toString() {
return name + " (" + age + " years old)";
}
}
class BubbleSortableList<T extends Comparable<T>> extends ArrayList<T> {
// Bubble sort implementation
public void bubbleSort() {
int n = size();
// Traverse through all elements
for (int i = 0; i < n - 1; i++) {
// Last i elements are already in place, so we can skip them
for (int j = 0; j < n - i - 1; j++) {
// Swap if the current element is greater than the next one
if (get(j).compareTo(get(j + 1)) > 0) {
T temp = get(j);
set(j, get(j + 1));
set(j + 1, temp);
}
}
}
}
}
public class Main {
public static void main(String[] args) {
BubbleSortableList<Person> persons = new BubbleSortableList<>();
persons.add(new Person("Alice", 25));
persons.add(new Person("Bob", 30));
persons.add(new Person("Charlie", 20));
persons.add(new Person("David", 35));
// unsorted
System.out.println("Unsorted List:");
for (Person person : persons) {
System.out.println(person);
}
// sort
persons.bubbleSort();
// sorted
System.out.println("\nSorted List (by age):");
for (Person person : persons) {
System.out.println(person);
}
}
}
Main.main(null);
Unsorted List:
Alice (25 years old)
Bob (30 years old)
Charlie (20 years old)
David (35 years old)
Sorted List (by age):
Charlie (20 years old)
Alice (25 years old)
Bob (30 years old)
David (35 years old)
Implementation
I am in charge of the statistics on dashboard page, where each player’s stats will be displayed.
I have implemented a prediction model already. The model is based on csapoints, but how can I test the the model is working correctly. If I sort the players by csa points and compare that list to a list of players sorted by AP Score prediction rank, the lists should be essentially the same. Here I can implement bubble sort on csapoints to sort the players and later use the sorted list as a verification tool of my model.
package com.nighthawk.spring_portfolio.mvc.person;
public class PersonSorter {
public static void bubbleSortByCsaPoints(Person[] persons) {
int n = persons.length;
boolean swapped;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
if (persons[i].getCsaPoints() > persons[i + 1].getCsaPoints()) {
// Swap persons[i] and persons[i+1]
Person temp = persons[i];
persons[i] = persons[i + 1];
persons[i + 1] = temp;
swapped = true;
}
}
} while (swapped);
}
public static void main(String[] args) {
// Obtain Person objects from initializer
Person[] persons = Person.init();
// Sort persons by csaPoints
bubbleSortByCsaPoints(persons);
// Print sorted persons
for (Person person : persons) {
System.out.println(person);
}
} }
</code>
Demo:
- run Person.Java
- run PersonSorter.Java