ALGORITHMIC PERFORMANCE REFLECTION AND QUICK SORT IN-DEPTH
THE FEEDBACK WE RECEIVED:
- Organized
- Liked the display of 2 algorithms side by side to make it easy to compare and show efficiency
- Nice projection of voice
REFLECTING ON OTHER GROUPS
-
Bubble Sort - This was Rachit’s group. The dating show idea was pretty funny and creative, and was still able to show aptly how the bubble sort worked in an easy way.
-
Merge Sort - Ethan’s group. His projection was really nice. Everyone splitting up into different clusters was important in helping me understand the merge sort.
-
Selection Sort - Paaras’s group. The rap was quite nice but the sort itself was kind of difficult to understand.
GANGSTER CLASS WITH COMPARABLE IMPLEMENTATION
// Gangster class, which implements the Comparable interface with type parameter Gangster
public class Gangster implements Comparable<Gangster> {
// gangster class private attributes
private String name; // gangster name
private String nickname; // stores gangster nickname
private int weight; // stores gangster's weight
// gangster object constructor
public Gangster(String name, String nickname, int weight) {
this.name = name; // initialize name attribute
this.nickname = nickname; // initialize nickname attribute
this.weight = weight; // initialize weight attribute
}
// name getter method
public String getName() {
return name;
}
// nickname getter method
public String getNickname() {
return nickname;
}
// weight getter
public int getweight() {
return weight;
}
// Override the toString() method to provide custom string representation of gangster object
@Override
public String toString() {
return String.format("%s a.k.a %s", name, nickname); // formatting of gangster nickname
}
// Override the compareTo() method to allow comparison of Gangster objects based on weight
@Override
public int compareTo(Gangster other) {
return Integer.compare(this.weight, other.weight); // compare weight of this gangster with another gangster
}
}
MAFIA CLASS
import java.util.ArrayList;
import java.util.Random;
// define mafia class
public class Mafia {
// private attribute for arraylist of gangster objects
private ArrayList<Gangster> mafia;
// constructor to initialize mafia object with a specified count of gangsters
public Mafia(int count) {
this.mafia = new ArrayList<>(); // Initialize the mafia ArrayList
populateMafia(count); // Populate the mafia with gangsters
}
// populating mafia with some gangsters ayyyy
private void populateMafia(int count) {
// Arrays of names and nicknames for gangsters
String[] names = {"Al Capone", "Lucky Luciano", "Vito Genovese", "Frank Costello", "Carlo Gambino", "Bugs Moran"};
String[] nicknames = {"Scarface", "Lucky", "Don Vito", "Prime Minister", "Don Carlo", "Buginson"};
Random random = new Random(); // random object for creating more random values
// populating mafia with gangsters
for (int i = 0; i < count; i++) {
int idx = random.nextInt(names.length); // Generate a random index for selecting a name and nickname
int weight = random.nextInt(10) + 1; // Generate a random weight (influence or power) for the gangster
mafia.add(new Gangster(names[idx], nicknames[idx], weight)); // Add a new gangster to the mafia
}
}
// perform bubble sort on mafia
public void bubbleSort() {
int n = mafia.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 weight and swap if necessary
if (mafia.get(j).compareTo(mafia.get(j + 1)) > 0) {
Gangster temp = mafia.get(j);
mafia.set(j, mafia.get(j + 1));
mafia.set(j + 1, temp);
}
}
}
}
// perform selection sort on mafia
public void selectionSort() {
int n = mafia.size(); // get mafia 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 gangsters by weight, updates minimum index if needed
if (mafia.get(j).compareTo(mafia.get(min_idx)) < 0)
min_idx = j;
}
// swaps the minimum element with the first element of the unsorted portion
Gangster temp = mafia.get(min_idx);
mafia.set(min_idx, mafia.get(i));
mafia.set(i, temp);
}
}
// insertion sort method on mafia
public void insertionSort() {
int n = mafia.size(); // get mafia size
// performing insertion sort
for (int i = 1; i < n; ++i) {
Gangster key = mafia.get(i); // current gangster is the key
int j = i - 1;
// moving elements of the mafia that are greater than key to one position ahead of their current position
while (j >= 0 && mafia.get(j).compareTo(key) > 0) {
mafia.set(j + 1, mafia.get(j));
j = j - 1;
}
mafia.set(j + 1, key); // put key at the right spot
}
}
// merge sort method
public void mergeSort() {
mergeSortHelper(0, mafia.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 mafia[].
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<Gangster> L = new ArrayList<>(n1);
ArrayList<Gangster> R = new ArrayList<>(n2);
// copy data to temp arraylists
for (int i = 0; i < n1; ++i)
L.add(i, mafia.get(left + i));
for (int j = 0; j < n2; ++j)
R.add(j, mafia.get(middle + 1 + j));
// merge temp arraylists into mafia[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L.get(i).compareTo(R.get(j)) <= 0) {
mafia.set(k, L.get(i));
i++;
} else {
mafia.set(k, R.get(j));
j++;
}
k++;
}
// copy any remaining elements
while (i < n1) {
mafia.set(k, L.get(i));
i++;
k++;
}
// copy any remaining elements
while (j < n2) {
mafia.set(k, R.get(j));
j++;
k++;
}
}
// perform quick sort on mafia
public void quickSort() {
quickSortHelper(0, mafia.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) {
Gangster pivot = mafia.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 (mafia.get(j).compareTo(pivot) < 0) {
i++;
// Swap mafia[i] and mafia[j]
Gangster temp = mafia.get(i);
mafia.set(i, mafia.get(j));
mafia.set(j, temp);
}
}
// swap mafia[i+1] and mafia[high] (or pivot)
Gangster temp = mafia.get(i + 1);
mafia.set(i + 1, mafia.get(high));
mafia.set(high, temp);
return i + 1;
}
// override toString() method to provide a string representation of mafia
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
// each gangsters information appended to StringBuilder
for (Gangster g : mafia) {
sb.append(g.toString()).append("\n");
}
return sb.toString(); // StringBuilder --> string and then return
}
// testing sorting algos
public static void main(String[] args) {
// Create a mafia with 10000 gangsters
Mafia mafia = new Mafia(10000);
// Timing Bubble Sort
long startTime = System.currentTimeMillis();
mafia.bubbleSort();
long endTime = System.currentTimeMillis();
System.out.println("Bubble Sort took: " + (endTime - startTime) + " ms");
// Recreate the mafia to reset the order of gangsters
mafia = new Mafia(10000);
// Timing Selection Sort
startTime = System.currentTimeMillis();
mafia.selectionSort();
endTime = System.currentTimeMillis();
System.out.println("Selection Sort took: " + (endTime - startTime) + " ms");
// Recreate the mafia
mafia = new Mafia(10000);
// Timing Insertion Sort
startTime = System.currentTimeMillis();
mafia.insertionSort();
endTime = System.currentTimeMillis();
System.out.println("Insertion Sort took: " + (endTime - startTime) + " ms");
// Recreate the mafia
mafia = new Mafia(10000);
// Timing Merge Sort
startTime = System.currentTimeMillis();
mafia.mergeSort();
endTime = System.currentTimeMillis();
System.out.println("Merge Sort took: " + (endTime - startTime) + " ms");
// Recreate the mafia
mafia = new Mafia(10000);
// Timing Quick Sort
startTime = System.currentTimeMillis();
mafia.quickSort();
endTime = System.currentTimeMillis();
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
}
}
Mafia.main(null);
Bubble Sort took: 250 ms
Selection Sort took: 160 ms
Insertion Sort took: 118 ms
Merge Sort took: 20 ms
Quick Sort took: 78 ms
GangsterList Class (Linked List Implementation):
import java.util.Random;
class Gangster implements Comparable<Gangster> {
private String name;
private String nickname;
private int weight;
public Gangster(String name, String nickname, int weight) {
this.name = name;
this.nickname = nickname;
this.weight = weight;
}
@Override
public int compareTo(Gangster other) {
return Integer.compare(this.weight, other.weight);
}
@Override
public String toString() {
return String.format("%s a.k.a %s (Weight: %d)", name, nickname, weight);
}
}
class GangsterNode {
Gangster data;
GangsterNode next;
public GangsterNode(Gangster data) {
this.data = data;
this.next = null;
}
}
class GangsterList {
private GangsterNode head;
public GangsterList() {
this.head = null;
}
public void add(Gangster data) {
GangsterNode newNode = new GangsterNode(data);
if (head == null) {
head = newNode;
} else {
GangsterNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void printList() {
GangsterNode 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(GangsterNode head, GangsterNode end) {
if (head != end && head != null && end != null) {
GangsterNode partitionNode = partition(head, end);
quickSortHelper(head, partitionNode);
quickSortHelper(partitionNode.next, end);
}
}
private GangsterNode partition(GangsterNode start, GangsterNode end) {
if (start == end || start == null || end == null)
return start;
GangsterNode pivotPrev = start;
GangsterNode curr = start;
Gangster pivot = end.data;
while (start != end) {
if (start.data.compareTo(pivot) < 0) {
pivotPrev = curr;
Gangster temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
Gangster temp = curr.data;
curr.data = pivot;
end.data = temp;
return pivotPrev;
}
private GangsterNode getTail(GangsterNode node) {
while (node != null && node.next != null) {
node = node.next;
}
return node;
}
public static void main(String[] args) {
GangsterList list = new GangsterList();
Random random = new Random();
// Names and nicknames for creating Gangster instances
String[] names = {"Al Capone", "Lucky Luciano", "Vito Genovese", "Frank Costello", "Carlo Gambino", "Bugs Moran"};
String[] nicknames = {"Scarface", "Lucky", "Don Vito", "Prime Minister", "Don Carlo", "Buginson"};
// Adding 10000 gangsters to the list
for (int i = 0; i < 10000; i++) {
int idx = random.nextInt(names.length);
int weight = random.nextInt(250) + 1; // random weights
list.add(new Gangster(names[idx], nicknames[idx], weight));
}
// 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();
}
}
GangsterList.main(null);
Quick Sort took: 5 ms