GOOD CODE
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.
public class Gangster implements Comparable<Gangster> {
private String name;
private String nickname;
private int influenceLevel; // A measure of the gangster's influence or power
public Gangster(String name, String nickname, int influenceLevel) {
this.name = name;
this.nickname = nickname;
this.influenceLevel = influenceLevel;
}
public String getName() {
return name;
}
public String getNickname() {
return nickname;
}
public int getInfluenceLevel() {
return influenceLevel;
}
@Override
public String toString() {
return String.format("%s a.k.a %s", name, nickname);
}
@Override
public int compareTo(Gangster other) {
return Integer.compare(this.influenceLevel, other.influenceLevel);
}
}
import java.util.ArrayList;
import java.util.Random;
public class Mafia {
private ArrayList<Gangster> mafia;
public Mafia(int count) {
this.mafia = new ArrayList<>();
populateMafia(count);
}
private void populateMafia(int count) {
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();
for (int i = 0; i < count; i++) {
int idx = random.nextInt(names.length);
int influenceLevel = random.nextInt(10) + 1;
mafia.add(new Gangster(names[idx], nicknames[idx], influenceLevel));
}
}
public void bubbleSort() {
int n = mafia.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
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);
}
}
}
}
public void selectionSort() {
int n = mafia.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (mafia.get(j).compareTo(mafia.get(min_idx)) < 0)
min_idx = j;
Gangster temp = mafia.get(min_idx);
mafia.set(min_idx, mafia.get(i));
mafia.set(i, temp);
}
}
public void insertionSort() {
int n = mafia.size();
for (int i = 1; i < n; ++i) {
Gangster key = mafia.get(i);
int j = i - 1;
while (j >= 0 && mafia.get(j).compareTo(key) > 0) {
mafia.set(j + 1, mafia.get(j));
j = j - 1;
}
mafia.set(j + 1, key);
}
}
public void mergeSort() {
mergeSortHelper(0, mafia.size() - 1);
}
private void mergeSortHelper(int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSortHelper(left, middle);
mergeSortHelper(middle + 1, right);
merge(left, middle, right);
}
}
private void merge(int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
ArrayList<Gangster> L = new ArrayList<>(n1);
ArrayList<Gangster> R = new ArrayList<>(n2);
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));
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++;
}
while (i < n1) {
mafia.set(k, L.get(i));
i++;
k++;
}
while (j < n2) {
mafia.set(k, R.get(j));
j++;
k++;
}
}
public void quickSort() {
quickSortHelper(0, mafia.size() - 1);
}
private void quickSortHelper(int low, int high) {
if (low < high) {
int pi = partition(low, high);
quickSortHelper(low, pi - 1);
quickSortHelper(pi + 1, high);
}
}
private int partition(int low, int high) {
Gangster pivot = mafia.get(high);
int i = (low - 1);
for (int j = low; j < high; j++) {
if (mafia.get(j).compareTo(pivot) < 0) {
i++;
Gangster temp = mafia.get(i);
mafia.set(i, mafia.get(j));
mafia.set(j, temp);
}
}
Gangster temp = mafia.get(i + 1);
mafia.set(i + 1, mafia.get(high));
mafia.set(high, temp);
return i + 1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Gangster g : mafia) {
sb.append(g.toString()).append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
// Create a mafia of size 2500
Mafia mafia = new Mafia(2500);
// 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(2500);
// 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(2500);
// 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(2500);
// 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(2500);
// Timing Quick Sort
startTime = System.currentTimeMillis();
mafia.quickSort();
endTime = System.currentTimeMillis();
System.out.println("Quick Sort took: " + (endTime - startTime) + " ms");
}
}
Main.main(null);
Bubble Sort took: 31 ms
Selection Sort took: 28 ms
Insertion Sort took: 20 ms
Merge Sort took: 3 ms
Quick Sort took: 7 ms
An Independent go at implementing Quick Sort with linked lists rather than arrays
import java.util.Random;
class Gangster implements Comparable<Gangster> {
private String name;
private String nickname;
private int influenceLevel;
public Gangster(String name, String nickname, int influenceLevel) {
this.name = name;
this.nickname = nickname;
this.influenceLevel = influenceLevel;
}
@Override
public int compareTo(Gangster other) {
return Integer.compare(this.influenceLevel, other.influenceLevel);
}
@Override
public String toString() {
return String.format("%s a.k.a %s (Influence: %d)", name, nickname, influenceLevel);
}
}
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 2500 gangsters to the list
for (int i = 0; i < 2500; i++) {
int idx = random.nextInt(names.length);
int influenceLevel = random.nextInt(100) + 1; // Influence levels between 1 and 100
list.add(new Gangster(names[idx], nicknames[idx], influenceLevel));
}
// 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: 1 ms
HORRENDOUS CODE BUT WE LEARN FROM OUR MISTAKES
Ganger and Mafia Object Setup
public class Gangster implements Comparable<Gangster> {
private String name;
private String nickname;
private int influenceLevel; // A measure of the gangster's influence or power
public Gangster(String name, String nickname, int influenceLevel) {
this.name = name;
this.nickname = nickname;
this.influenceLevel = influenceLevel;
}
public String getName() {
return name;
}
public String getNickname() {
return nickname;
}
public int getInfluenceLevel() {
return influenceLevel;
}
@Override
public String toString() {
return String.format("%s a.k.a %s", name, nickname);
}
@Override
public int compareTo(Gangster other) {
return Integer.compare(this.influenceLevel, other.influenceLevel);
}
}
import java.util.ArrayList;
public class Mafia {
public static ArrayList<Gangster> generate() {
ArrayList<Gangster> mafia = new ArrayList<>();
mafia.add(new Gangster("Al Capone", "Scarface", 10));
mafia.add(new Gangster("Lucky Luciano", "Lucky", 9));
mafia.add(new Gangster("Vito Genovese", "Don Vito", 8));
mafia.add(new Gangster("Frank Costello", "Prime Minister", 7));
mafia.add(new Gangster("Carlo Gambino", "Don Carlo", 6));
mafia.add(new Gangster("Bugs Moran", "Buginson", 9));
return mafia;
}
}
Bubble Sort
public class BubbleSort {
public static void bubbleSort(ArrayList<Gangster> list) {
int n = list.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (list.get(j).compareTo(list.get(j + 1)) > 0) {
Gangster temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
}
ArrayList<Gangster> mafia = Mafia.generate();
System.out.println("Mafia before sort: " + mafia);
BubbleSort.bubbleSort(mafia);
System.out.println("Mafia after sort: " + mafia);
Mafia before sort: [Al Capone a.k.a Scarface, Lucky Luciano a.k.a Lucky, Vito Genovese a.k.a Don Vito, Frank Costello a.k.a Prime Minister, Carlo Gambino a.k.a Don Carlo, Bugs Moran a.k.a Buginson]
Mafia after sort: [Carlo Gambino a.k.a Don Carlo, Frank Costello a.k.a Prime Minister, Vito Genovese a.k.a Don Vito, Lucky Luciano a.k.a Lucky, Bugs Moran a.k.a Buginson, Al Capone a.k.a Scarface]
Selection Sort
public class SelectionSort {
public static void selectionSort(ArrayList<Gangster> list) {
int n = list.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (list.get(j).compareTo(list.get(minIndex)) < 0) {
minIndex = j;
}
}
Gangster temp = list.get(minIndex);
list.set(minIndex, list.get(i));
list.set(i, temp);
}
}
}
ArrayList<Gangster> mafia = Mafia.generate();
System.out.println("Mafia before Selection Sort: " + mafia);
SelectionSort.selectionSort(mafia);
System.out.println("Mafia after Selection Sort: " + mafia);
Mafia before Selection Sort: [Al Capone a.k.a Scarface, Lucky Luciano a.k.a Lucky, Vito Genovese a.k.a Don Vito, Frank Costello a.k.a Prime Minister, Carlo Gambino a.k.a Don Carlo, Bugs Moran a.k.a Buginson]
Mafia after Selection Sort: [Carlo Gambino a.k.a Don Carlo, Frank Costello a.k.a Prime Minister, Vito Genovese a.k.a Don Vito, Lucky Luciano a.k.a Lucky, Bugs Moran a.k.a Buginson, Al Capone a.k.a Scarface]
Insertion Sort
public class InsertionSort {
public static void insertionSort(ArrayList<Gangster> list) {
int n = list.size();
for (int i = 1; i < n; i++) {
Gangster key = list.get(i);
int j = i - 1;
while (j >= 0 && list.get(j).compareTo(key) > 0) {
list.set(j + 1, list.get(j));
j--;
}
list.set(j + 1, key);
}
}
}
ArrayList<Gangster> mafia = Mafia.generate();
System.out.println("Mafia before Insertion Sort: " + mafia);
InsertionSort.insertionSort(mafia);
System.out.println("Mafia after Insertion Sort: " + mafia);
Mafia before Insertion Sort: [Al Capone a.k.a Scarface, Lucky Luciano a.k.a Lucky, Vito Genovese a.k.a Don Vito, Frank Costello a.k.a Prime Minister, Carlo Gambino a.k.a Don Carlo, Bugs Moran a.k.a Buginson]
Mafia after Insertion Sort: [Carlo Gambino a.k.a Don Carlo, Frank Costello a.k.a Prime Minister, Vito Genovese a.k.a Don Vito, Lucky Luciano a.k.a Lucky, Bugs Moran a.k.a Buginson, Al Capone a.k.a Scarface]
Merge Sort
public class MergeSort {
public static void mergeSort(ArrayList<Gangster> list) {
if (list.size() > 1) {
int mid = list.size() / 2;
ArrayList<Gangster> left = new ArrayList<>(list.subList(0, mid));
ArrayList<Gangster> right = new ArrayList<>(list.subList(mid, list.size()));
mergeSort(left);
mergeSort(right);
merge(list, left, right);
}
}
private static void merge(ArrayList<Gangster> list, ArrayList<Gangster> left, ArrayList<Gangster> right) {
int i = 0, j = 0, k = 0;
while (i < left.size() && j < right.size()) {
if (left.get(i).compareTo(right.get(j)) <= 0) {
list.set(k++, left.get(i++));
} else {
list.set(k++, right.get(j++));
}
}
while (i < left.size()) {
list.set(k++, left.get(i++));
}
while (j < right.size()) {
list.set(k++, right.get(j++));
}
}
}
ArrayList<Gangster> mafia = Mafia.generate();
System.out.println("Mafia before Merge Sort: " + mafia);
MergeSort.mergeSort(mafia);
System.out.println("Mafia after Merge Sort: " + mafia);
Mafia before Merge Sort: [Al Capone a.k.a Scarface, Lucky Luciano a.k.a Lucky, Vito Genovese a.k.a Don Vito, Frank Costello a.k.a Prime Minister, Carlo Gambino a.k.a Don Carlo, Bugs Moran a.k.a Buginson]
Mafia after Merge Sort: [Carlo Gambino a.k.a Don Carlo, Frank Costello a.k.a Prime Minister, Vito Genovese a.k.a Don Vito, Lucky Luciano a.k.a Lucky, Bugs Moran a.k.a Buginson, Al Capone a.k.a Scarface]
Quicksort wirth Arrays
public class QuickSort {
public static void quickSort(ArrayList<Gangster> list, int low, int high) {
if (low < high) {
int pi = partition(list, low, high);
quickSort(list, low, pi - 1);
quickSort(list, pi + 1, high);
}
}
private static int partition(ArrayList<Gangster> list, int low, int high) {
Gangster pivot = list.get(high);
int i = low - 1;
for (int j = low; j < high; j++) {
if (list.get(j).compareTo(pivot) < 0) {
i++;
Gangster temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
Gangster temp = list.get(i + 1);
list.set(i + 1, list.get(high));
list.set(high, temp);
return i + 1;
}
}
ArrayList<Gangster> mafia = Mafia.generate();
System.out.println("Mafia before Quick Sort: " + mafia);
QuickSort.quickSort(mafia, 0, mafia.size() - 1);
System.out.println("Mafia after Quick Sort: " + mafia);
Mafia before Quick Sort: [Al Capone a.k.a Scarface, Lucky Luciano a.k.a Lucky, Vito Genovese a.k.a Don Vito, Frank Costello a.k.a Prime Minister, Carlo Gambino a.k.a Don Carlo, Bugs Moran a.k.a Buginson]
Mafia after Quick Sort: [Carlo Gambino a.k.a Don Carlo, Frank Costello a.k.a Prime Minister, Vito Genovese a.k.a Don Vito, Bugs Moran a.k.a Buginson, Lucky Luciano a.k.a Lucky, Al Capone a.k.a Scarface]
Quicksort with Linked Lists
public class GangsterNode {
Gangster data;
GangsterNode next;
public GangsterNode(Gangster data) {
this.data = data;
this.next = null;
}
}
public class GangsterList {
GangsterNode head;
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 class QuickSortLinkedList {
public static void quickSort(GangsterNode head, GangsterNode end) {
if (head != end && head != null && end != null) {
GangsterNode partitionNode = partition(head, end);
quickSort(head, partitionNode);
quickSort(partitionNode.next, end);
}
}
private static 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;
// Iterate till one before the end, exclusive of the end
while (start != end) {
if (start.data.compareTo(pivot) < 0) {
// Keep tracks of last modified item
pivotPrev = curr;
Gangster temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
// Swap the position of the current node and pivot
Gangster temp = curr.data;
curr.data = pivot;
end.data = temp;
// Return one before pivot, because pivot is now in its correct place
return pivotPrev;
}
public static void main(String[] args) {
GangsterList list = new GangsterList();
list.add(new Gangster("Al Capone", "Scarface", 10));
list.add(new Gangster("Lucky Luciano", "Lucky", 9));
list.add(new Gangster("Vito Genovese", "Don Vito", 8));
list.add(new Gangster("Frank Costello", "Prime Minister", 7));
list.add(new Gangster("Carlo Gambino", "Don Carlo", 6));
System.out.println("Original list:");
list.printList();
// Finding the last node
GangsterNode last = list.head;
while (last.next != null)
last = last.next;
// Applying quick sort
quickSort(list.head, last);
System.out.println("Sorted list:");
list.printList();
}
}
QuickSortLinkedList.main(null);
Original list:
Al Capone a.k.a Scarface -> Lucky Luciano a.k.a Lucky -> Vito Genovese a.k.a Don Vito -> Frank Costello a.k.a Prime Minister -> Carlo Gambino a.k.a Don Carlo -> null
Sorted list:
Carlo Gambino a.k.a Don Carlo -> Frank Costello a.k.a Prime Minister -> Vito Genovese a.k.a Don Vito -> Lucky Luciano a.k.a Lucky -> Al Capone a.k.a Scarface -> null