Prep Work
Thursday
- I reviewed the script and briefly looked at the quick sort to understand the sorting part
- I am the grunt so my main job is to dance around and know how to sort myself
- Need to learn how to do my sort more and things of that nature
Friday (Lunch)
- I could not make it to the after school meeting, but only the lunch meeting
- We reviewed the sorting procedures and how to do them
- Went over the script and our roles in each part
Monday
- We met at lunch and tutorial to go over what to do in the presentation
- We did a couple run throughs and things of that nature
- Need to work on our presentation and cohesiveness
Tuesday
- Last meeting at tutorial
- Did our last rehearsal
- Went over the script stuff at night so we are ready to go
// makes a person class with the Comparable
class Person implements Comparable<Person> {
private String name;
private int age;
//setters and getters
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
// converts it to a string
@Override
public String toString() {
return name + " (" + age + ")";
}
//compares the name then age and returns -1, 0 or 1
@Override
public int compareTo(Person other) {
// Compare names first
int nameComparison = this.name.compareTo(other.name);
// If names are different, return the result of comparing names
if (nameComparison != 0) {
return nameComparison;
}
// If names are the same, compare ages
return Integer.compare(this.age, other.age);
}
}
public class Team {
// private attribute for arraylist of Person objects
private ArrayList<Person> team;
// constructor to initialize team object with a specified count of Persons
public Team(int count) {
this.team = new ArrayList<>(); // Initialize the team ArrayList
populateTeam(count); // Populate the team with Persons
}
// populating team with some Persons ayyyy
private void populateTeam(int count) {
// Arrays of names and nicknames for Persons
String[] names = {"Kaiden", "Bob", "Bill", "Derrick", "Nikhil", "Alfred", "Bruce","Sir Kevin Du","Alexander", "Jimbo","Jumbo","Pumba","Simba","Mufasa","Bob","Scar","Batman"};
Random random = new Random(); // random object for creating more random values
// populating team with Persons
for (int i = 0; i < count; i++) {
int idx = random.nextInt(names.length); // Generate a random index for selecting a name and nickname
int age = random.nextInt(20) + 1; // Generate a random age (influence or power) for the Person
team.add(new Person(names[idx], age)); // Add a new Person to the team
}
}
public void bubbleSort() {
int n = team.size(); // mafia size
// bubble sort algo
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
// compare adjacent gangsters by name or age and swap if necessary
if (team.get(j).compareTo(team.get(j + 1)) > 0) {
Person temp = team.get(j);
team.set(j, team.get(j + 1));
team.set(j + 1, temp);
}
}
}
}
public void selectionSort() {
int n = team.size(); // get team size
// perform selection sort algorithm
for (int i = 0; i < n - 1; i++) {
int min_idx = i; // current index = minimum index
// finds minimum element in unsorted portion
for (int j = i + 1; j < n; j++) {
// compares Persons by name or age, updates minimum index if needed
if (team.get(j).compareTo(team.get(min_idx)) < 0)
min_idx = j;
}
// swaps the minimum element with the first element of the unsorted portion
Person temp = team.get(min_idx);
team.set(min_idx, team.get(i));
team.set(i, temp);
}
}
public void insertionSort() {
int n = team.size(); // get team size
// performing insertion sort
for (int i = 1; i < n; ++i) {
Person key = team.get(i); // current Person is the key
int j = i - 1;
// moving elements of the team that are greater than key to one position ahead of their current position
while (j >= 0 && team.get(j).compareTo(key) > 0) {
team.set(j + 1, team.get(j));
j = j - 1;
}
team.set(j + 1, key); // put key at the right spot
}
}
// merge sort method
public void mergeSort() {
mergeSortHelper(0, team.size() - 1); // helper method to perform sort
}
// helps perform merge sort recursively
private void mergeSortHelper(int left, int right) {
if (left < right) {
int middle = (left + right) / 2; // find middle index
mergeSortHelper(left, middle); // sort left half
mergeSortHelper(middle + 1, right); // sort right half
merge(left, middle, right); // merge sorted halves
}
}
// merge two subarrays of team[].
private void merge(int left, int middle, int right) {
// calculate two subarrays sizes
int n1 = middle - left + 1;
int n2 = right - middle;
// create temp ArrayLists to hold subarrays
ArrayList<Person> L = new ArrayList<>(n1);
ArrayList<Person> R = new ArrayList<>(n2);
// copy data to temp arraylists
for (int i = 0; i < n1; ++i)
L.add(i, team.get(left + i));
for (int j = 0; j < n2; ++j)
R.add(j, team.get(middle + 1 + j));
// merge temp arraylists into team[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L.get(i).compareTo(R.get(j)) <= 0) {
team.set(k, L.get(i));
i++;
} else {
team.set(k, R.get(j));
j++;
}
k++;
}
// copy any remaining elements
while (i < n1) {
team.set(k, L.get(i));
i++;
k++;
}
// copy any remaining elements
while (j < n2) {
team.set(k, R.get(j));
j++;
k++;
}
}
// perform quick sort on team
public void quickSort() {
quickSortHelper(0, team.size() - 1); // call helper method to do quick sort
}
// helper method
private void quickSortHelper(int low, int high) {
if (low < high) {
int pi = partition(low, high); // get partition index
quickSortHelper(low, pi - 1); // sort left part of subarray
quickSortHelper(pi + 1, high); // sort right part of subarray
}
}
// method to partition array and return the partitioning index
private int partition(int low, int high) {
Person pivot = team.get(high); // select pivot
int i = (low - 1); // smaller element's index
// loop to partition array
for (int j = low; j < high; j++) {
// if current element is smaller than pivot
if (team.get(j).compareTo(pivot) < 0) {
i++;
// Swap team[i] and team[j]
Person temp = team.get(i);
team.set(i, team.get(j));
team.set(j, temp);
}
}
// swap team[i+1] and team[high] (or pivot)
Person temp = team.get(i + 1);
team.set(i + 1, team.get(high));
team.set(high, temp);
return i + 1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
// each Persons information appended to StringBuilder
for (Person p : team) {
sb.append(p.toString()).append("\n");
}
return sb.toString(); // StringBuilder --> string and then return
}
// testing sorting algos
public static void main(String[] args) {
// Create a team with 10000 Persons
Team team = new Team(10000);
// Timing Bubble Sort
long startTime = System.currentTimeMillis();
team.bubbleSort();
long endTime = System.currentTimeMillis();
System.out.println("Bubble Sort took: " + (endTime - startTime) + " ms");
// Recreate the team to reset the order of Persons
team = new Team(10000);
// Timing Selection Sort
startTime = System.currentTimeMillis();
team.selectionSort();
endTime = System.currentTimeMillis();
System.out.println("Selection Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(10000);
// Timing Insertion Sort
startTime = System.currentTimeMillis();
team.insertionSort();
endTime = System.currentTimeMillis();
System.out.println("Insertion Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(10000);
// Timing Merge Sort
startTime = System.currentTimeMillis();
team.mergeSort();
endTime = System.currentTimeMillis();
System.out.println("Merge Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(10000);
// Timing Quick Sort
startTime = System.currentTimeMillis();
team.quickSort();
endTime = System.currentTimeMillis();
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
}
public static void main2(String[] args) {
// Create a team with 10000 Persons
Team team = new Team(5);
// Timing Bubble Sort
System.out.println("");
System.out.println("Unsorted team:");
System.out.println(team);
System.out.println("");
long startTime = System.currentTimeMillis();
team.bubbleSort();
long endTime = System.currentTimeMillis();
System.out.println("Sorted team:");
System.out.println(team);
System.out.println("Bubble Sort took: " + (endTime - startTime) + " ms");
// Recreate the team to reset the order of Persons
team = new Team(5);
// Timing Bubble Sort
System.out.println("");
System.out.println("Unsorted team:");
System.out.println(team);
System.out.println("");
startTime = System.currentTimeMillis();
team.selectionSort();
endTime = System.currentTimeMillis();
System.out.println("Sorted team:");
System.out.println(team);
System.out.println("Selection Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(5);
// Timing Bubble Sort
System.out.println("");
System.out.println("Unsorted team:");
System.out.println(team);
System.out.println("");
startTime = System.currentTimeMillis();
team.insertionSort();
endTime = System.currentTimeMillis();
System.out.println("Sorted team:");
System.out.println(team);
System.out.println("Insertion Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(5);
// Timing Bubble Sort
System.out.println("");
System.out.println("Unsorted team:");
System.out.println(team);
System.out.println("");
startTime = System.currentTimeMillis();
team.mergeSort();
endTime = System.currentTimeMillis();
System.out.println("Sorted team:");
System.out.println(team);
System.out.println("Merge Sort took: " + (endTime - startTime) + " ms");
// Recreate the team
team = new Team(5);
// Timing Bubble Sort
System.out.println("");
System.out.println("Unsorted team:");
System.out.println(team);
System.out.println("");
startTime = System.currentTimeMillis();
team.quickSort();
endTime = System.currentTimeMillis();
System.out.println("Sorted team:");
System.out.println(team);
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
}
}
Team.main(null);
Team.main2(null);
Bubble Sort took: 707 ms
Selection Sort took: 339 ms
Insertion Sort took: 244 ms
Merge Sort took: 22 ms
Quick Sort took: 9 ms
Unsorted team:
Bob (16)
Batman (13)
Bob (5)
Batman (13)
Mufasa (3)
Sorted team:
Batman (13)
Batman (13)
Bob (5)
Bob (16)
Mufasa (3)
Bubble Sort took: 0 ms
Unsorted team:
Sir Kevin Du (12)
Alfred (5)
Simba (14)
Jumbo (4)
Simba (16)
Sorted team:
Alfred (5)
Jumbo (4)
Simba (14)
Simba (16)
Sir Kevin Du (12)
Selection Sort took: 0 ms
Unsorted team:
Alexander (2)
Pumba (8)
Nikhil (4)
Pumba (15)
Alexander (8)
Sorted team:
Alexander (2)
Alexander (8)
Nikhil (4)
Pumba (8)
Pumba (15)
Insertion Sort took: 0 ms
Unsorted team:
Jumbo (15)
Bill (5)
Alfred (3)
Nikhil (13)
Scar (9)
Sorted team:
Alfred (3)
Bill (5)
Jumbo (15)
Nikhil (13)
Scar (9)
Merge Sort took: 0 ms
Unsorted team:
Bruce (11)
Kaiden (20)
Kaiden (19)
Simba (11)
Bob (12)
Sorted team:
Bob (12)
Bruce (11)
Kaiden (19)
Kaiden (20)
Simba (11)
Quick Sort took: 0 ms
Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted.
Selection Sort
Selection sort is a simple sorting algorithm that divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It repeatedly finds the smallest (or largest, depending on the sorting order) element from the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists and it inserts each item one at a time at its designated spot.
Merge Sort
Merge sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts the two halves independently, and then merges the sorted halves. It is one of the most efficient comparison-based sorting algorithms with a time complexity of O(n log n) in the worst-case scenario.
Quick Sort
Quick sort is a divide-and-conquer 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 sorted recursively.
Reflection: Our Video
At the presentation day I think our group was a very fun and exciting presentation. One thing that we could have improved on was making the numbers on the papers easier to see. Comparing ourselves to the other groups, I would think we were the second best after the pick up line sorting algorithm. Also in my opinion, the pool noodle one was kind of boring and confusing. In the murder mystery one, it was cool, but kind of corny. Regarding the practices and learning about the sorting methods, I think this activity is great for learning your own sort, but not everyone’s presentations of the sorts were good, so if you were completely new on learning the other sorts, some extra learning would be needed to understand the sorts. Overall, I think the algorythmic activity is a fun and good portion of the class.
import java.util.Random;
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
// Compare names first
int nameComparison = this.name.compareTo(other.name);
// If names are different, return the result of comparing names
if (nameComparison != 0) {
return nameComparison;
}
// If names are the same, compare ages
return Integer.compare(this.age, other.age);
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
class PersonNode {
Person data;
PersonNode next;
public PersonNode(Person data) {
this.data = data;
this.next = null;
}
}
class PersonList {
private PersonNode head;
public PersonList() {
this.head = null;
}
public void add(Person data) {
PersonNode newNode = new PersonNode(data);// adding the new nodes or people to the list
if (head == null) {
head = newNode;
} else {
PersonNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void printList() {
PersonNode temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
public void quickSort() {
quickSortHelper(head, getTail(head));
}
private void quickSortHelper(PersonNode head, PersonNode end) { // comparing the nodes to each other
if (head != end && head != null && end != null) {
PersonNode partitionNode = partition(head, end);
quickSortHelper(head, partitionNode);
quickSortHelper(partitionNode.next, end);
}
}
private PersonNode partition(PersonNode start, PersonNode end) {
if (start == end || start == null || end == null)
return start;
PersonNode pivotPrev = start;
PersonNode curr = start;
Person pivot = end.data;
while (start != end) {
if (start.data.compareTo(pivot) < 0) {
pivotPrev = curr;
Person temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
Person temp = curr.data;
curr.data = pivot;
end.data = temp;
return pivotPrev;
}
private PersonNode getTail(PersonNode node) {
while (node != null && node.next != null) {
node = node.next;
}
return node;
}
public static void main(String[] args) {
PersonList list = new PersonList();
Random random = new Random();
// Names and nicknames for creating Person instances
String[] names = {"Kaiden", "Bob", "Bill", "Derrick", "Nikhil", "Alfred", "Bruce","Sir Kevin Du","Alexander", "Jimbo","Jumbo","Pumba","Simba","Mufasa","Bob","Scar","Batman"};
// Adding 10000 gangsters to the list
for (int i = 0; i < 10000; i++) {
int idx = random.nextInt(names.length); // Generate a random index for selecting a name and nickname
int age = random.nextInt(20) + 1; // Generate a random age (influence or power) for the Person
list.add(new Person(names[idx], age));
}
// Timing the quick sort algorithm
long startTime = System.currentTimeMillis();
list.quickSort();
long endTime = System.currentTimeMillis();
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
// Optionally print the sorted list to verify
//list.printList();
}
public static void main2(String[] args) {
PersonList list = new PersonList();
Random random = new Random();
// Names and nicknames for creating Person instances
String[] names = {"Kaiden", "Bob", "Bill", "Derrick", "Nikhil", "Alfred", "Bruce","Sir Kevin Du","Alexander", "Jimbo","Jumbo","Pumba","Simba","Mufasa","Bob","Scar","Batman"};
// Adding 10000 gangsters to the list
for (int i = 0; i < 10; i++) {
int idx = random.nextInt(names.length); // Generate a random index for selecting a name and nickname
int age = random.nextInt(20) + 1; // Generate a random age (influence or power) for the Person
list.add(new Person(names[idx], age));
}
// Timing the quick sort algorithm
long startTime = System.currentTimeMillis();
list.quickSort();
long endTime = System.currentTimeMillis();
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
// Optionally print the sorted list to verify
list.printList();
}
}
PersonList.main(null);
PersonList.main2(null);
Quick Sort took: 9 ms
Quick Sort took: 0 ms
Alexander (7) -> Batman (9) -> Bill (11) -> Bill (16) -> Bob (16) -> Derrick (6) -> Jimbo (2) -> Mufasa (9) -> Pumba (9) -> Pumba (11) -> null