Algorythmic Sorts

Algorythmic Dance

Today (April 3), my group along with four other groups got to perform each of our sorting algorithms in front of the judges as well as people who happened to be interested in watching us perform. I enjoyed watching every single performance, as I was amazed at all of the groups were able to get creative with showing off their sorting algorithms in their own unique way. For example, the insertion sort algorithm performance was pretty cool in that it used rap lyrics as well as a beach theme in order to convey the mechanisms of insertion sort. Also, the bubble sort performance was funny to me and many others who attended the event since the theme was centered around a dating show and a person wanting to figure out who their best match is.

In terms of our own performance, I thought that everyone (including me) did an amazing job. I feel like all of us were punctual whenever we were practicing, whether it was at lunch, during class, or outside of school. Ultimately, all of those practice sessions played of in the end, as we were able to perform on the stage without any issues and earned two 10/10s and 3 9/10s from the judges, which is quite amazing. We ended up in 3rd place for total scores, which we all agreed was a pretty solid ranking.

We ended up posting our practice sessions on our Instagram account, which actually ended up earning a lot of followers and views (and most importantly, likes!)

Here are some captures of our practice sessions!

There are 5 practice for the dance, and I all participated on all of group meeting.

Code for class

import java.util.ArrayList;
import java.util.List;

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;
    }
    
    public abstract String toString();

    // compare this.toString with toString objects
    public int compareTo(Collectable c) {
        return this.toString().compareTo(c.toString());
    }
}

public class Flower extends Collectable {
    // Class data
    public static KeyTypes key; // static initializer
    public static void setOrder(KeyTypes key) { Flower.key = key; }
    public enum KeyType implements KeyTypes { name, petals, all}

    private final String name;
    private final int petals;

    // constructor
    Flower(String name, int petals) {
        this.setType("Flower");
        this.name = name;
        this.petals = petals;
    }
    
    @Override
    protected KeyTypes getKey() {
        return Flower.key;
    }
    
    @Override
    public String toString() {
        StringBuilder jsonBuilder = new StringBuilder();
        if (KeyType.name.equals(this.getKey())) {
        jsonBuilder.append("\"name\": \"").append(this.name).append("\"");
        } else if (KeyType.petals.equals(this.getKey())) {
        jsonBuilder.append("\"petals\": ").append(this.petals).append("");
        } else {
            jsonBuilder.append("\"name\": \"").append(this.name).append("\"");
            jsonBuilder.append("\"petals\": ").append(this.petals).append("");
        }
        return jsonBuilder.toString();
    }

    public void print() {
        System.out.println(name + ": " + petals);
    }

    public static void bubbleSort(List<Collectable> 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) {
                    Collectable temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }
    
    public static List<Collectable> flowers() {
        List<Collectable> flowers = new ArrayList<>();
        flowers.add(new Flower("E", 5));
        flowers.add(new Flower("D", 3));
        flowers.add(new Flower("B", 7));
        flowers.add(new Flower("C", 2));
        flowers.add(new Flower("A", 4));
        return flowers;
    }

    
}
List<Collectable> flowers = Flower.flowers();

Flower.setOrder(Flower.KeyType.all);
System.out.println("Original: ");
System.out.println(flowers.toString());
System.out.println("-----------------name-------------------");
Flower.setOrder(Flower.KeyType.name);
System.out.println("Before sorting:");
System.out.println(flowers.toString());
        
Flower.bubbleSort(flowers);
System.out.println("\nAfter sorting:");
System.out.println(flowers.toString());

System.out.println("-----------------petals-------------------");

Flower.setOrder(Flower.KeyType.petals);
System.out.println("Before sorting:");
System.out.println(flowers.toString());
        
Flower.bubbleSort(flowers);
System.out.println("\nAfter sorting:");
System.out.println(flowers.toString());

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------


Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

bubble sort

import java.util.List;

public class BubbleSort {
    public static void bubbleSort(List<Collectable> list) {
        int n = list.size();
        // iteration
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // compare j elements and j+1 elements
                if (list.get(j).compareTo(list.get(j + 1)) > 0) {
                    // swap index
                    Collectable temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }
    
    public static void main(String[] args) {
       
        List<Collectable> list = Flower.flowers();
        Flower.setOrder(Flower.KeyType.all);
        System.out.println("Original: ");
        System.out.println(list.toString());

        System.out.println("-----------------name-------------------");
        Flower.setOrder(Flower.KeyType.name); // set key as name
        System.out.println("Before sorting:");
        System.out.println(list.toString());

        bubbleSort(list); // sorted in alphabet
        System.out.println("\nAfter sorting:");
        System.out.println(list.toString());

        System.out.println("-----------------petals-------------------");

        Flower.setOrder(Flower.KeyType.petals);
        System.out.println("Before sorting:");
        System.out.println(list.toString());

        bubbleSort(list); // sorted in Integer 
        System.out.println("\nAfter sorting:");
        System.out.println(list.toString());
    }
}


BubbleSort.main(null);

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------
Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

Selection Sort

import java.util.List;

public class SelectionSort {
    public static void selectionSort(List<Collectable> 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;
                }
            }
            Collectable temp = list.get(minIndex);
            list.set(minIndex, list.get(i));
            list.set(i, temp);
        }
    }
    
    public static void main(String[] args) {
       
        List<Collectable> list = Flower.flowers();
        Flower.setOrder(Flower.KeyType.all);
        System.out.println("Original: ");
        System.out.println(list.toString());

        System.out.println("-----------------name-------------------");
        Flower.setOrder(Flower.KeyType.name);
        System.out.println("Before sorting:");
        System.out.println(list);

        selectionSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list.toString());

        System.out.println("-----------------petals-------------------");

        Flower.setOrder(Flower.KeyType.petals);
        System.out.println("Before sorting:");
        System.out.println(list);

        selectionSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list);
    }
}


BubbleSort.main(null);

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------
Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

Insertion Sort

import java.util.List;

public class InsertionSort {
    public static void insertionSort(List<Collectable> list) {
        int n = list.size();
        for (int i = 1; i < n; ++i) {
            Collectable 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);
        }
    }

    public static void main(String[] args) {
       
        List<Collectable> list = Flower.flowers();
        Flower.setOrder(Flower.KeyType.all);
        System.out.println("Original: ");
        System.out.println(list.toString());

        System.out.println("-----------------name-------------------");
        Flower.setOrder(Flower.KeyType.name);
        System.out.println("Before sorting:");
        System.out.println(list);

        insertionSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list.toString());

        System.out.println("-----------------petals-------------------");

        Flower.setOrder(Flower.KeyType.petals);
        System.out.println("Before sorting:");
        System.out.println(list);

        insertionSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list);
    }
}

InsertionSort.main(null);

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------
Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

Merge Sort

import java.util.List;

public class MergeSort {
    public static void mergeSort(List<Collectable> list) {
        if (list.size() > 1) {
            int mid = list.size() / 2;
            List<Collectable> left = new ArrayList<>(list.subList(0, mid)); 
            List<Collectable> right = new ArrayList<>(list.subList(mid, list.size()));

            mergeSort(left); 
            mergeSort(right); 

            merge(list, left, right); 
        }
    }
    private static void merge(List<Collectable> list, List<Collectable> left, List<Collectable> 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++));
        }
    }

    public static void main(String[] args) {
       
        List<Collectable> list = Flower.flowers();
        Flower.setOrder(Flower.KeyType.all);
        System.out.println("Original: ");
        System.out.println(list.toString());

        System.out.println("-----------------name-------------------");
        Flower.setOrder(Flower.KeyType.name);
        System.out.println("Before sorting:");
        System.out.println(list);

        mergeSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list.toString());

        System.out.println("-----------------petals-------------------");

        Flower.setOrder(Flower.KeyType.petals);
        System.out.println("Before sorting:");
        System.out.println(list);

        mergeSort(list);
        System.out.println("\nAfter sorting:");
        System.out.println(list);
    }
}

MergeSort.main(null);

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------
Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

Quick Sort

import java.util.List;

public class QuickSort {
    public static void quickSort(List<Collectable> list, int low, int high) {
        if (low < high) {
            int pi = partition(list, low, high);
            quickSort(list, low, pi - 1);
            quickSort(list, pi + 1, high);
        }
    }

    public static int partition(List<Collectable> list, int low, int high) {
        Collectable pivot = list.get(high);
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (list.get(j).compareTo(pivot) < 0) {
                i++;
                Collectable temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }
        Collectable temp = list.get(i + 1);
        list.set(i + 1, list.get(high));
        list.set(high, temp);

        return i + 1;
    }

    
}

List<Collectable> list = Flower.flowers();
Flower.setOrder(Flower.KeyType.all);   
System.out.println("Original: ");
System.out.println(list.toString());

System.out.println("-----------------name-------------------");
Flower.setOrder(Flower.KeyType.name);
System.out.println("Before sorting:");
System.out.println(list);

QuickSort.quickSort(list, 0, list.size() - 1);
System.out.println("\nAfter sorting:");
System.out.println(list.toString());

System.out.println("-----------------petals-------------------");

Flower.setOrder(Flower.KeyType.petals);
System.out.println("Before sorting:");
System.out.println(list);

QuickSort.quickSort(list, 0, list.size() - 1);
System.out.println("\nAfter sorting:");
System.out.println(list);

Original: 
["name": "E""petals": 5, "name": "D""petals": 3, "name": "B""petals": 7, "name": "C""petals": 2, "name": "A""petals": 4]
-----------------name-------------------
Before sorting:
["name": "E", "name": "D", "name": "B", "name": "C", "name": "A"]

After sorting:
["name": "A", "name": "B", "name": "C", "name": "D", "name": "E"]
-----------------petals-------------------
Before sorting:
["petals": 4, "petals": 7, "petals": 2, "petals": 3, "petals": 5]

After sorting:
["petals": 2, "petals": 3, "petals": 4, "petals": 5, "petals": 7]

Determine the pivot (reference point) -> It doesn’t matter if you set any standard -> Designate the midpoint as the reference point and proceed.
Call quickSort(Start, End) -> initially Start = 0, End = n - 1
Left starts at Start and increases until it reaches a number greater than or equal to pivot.
Rigth starts at the end and decreases until it reaches a number less than or equal to the pivot.
If Left <= Right, change the two numbers, increase Left, decrease Right, and then increase and decrease Left and Right again to find. When Left > Right
If Right > Start, call quickSort(Start, Right)
If Left < End, call quickSort(Left, End) (separate sections)
Proceed with this operation until the length of all separated sections becomes 1 -> Sorting is complete. Time complexity: O(nlogn), worst case: O(n^2)
ex) Assume you want to sort 5 1 6 3 4 2 7 quickSort(0,6) => Start = 0, End = 6, pivot = arr[ (0 + 6) / 2 ] = arr[ 3 ] = 3 Left starts from 0 and increases until it encounters a number greater than 3, and stops when it encounters 5 -> Left = 0 Right starts at 6 and decreases until it encounters a number less than 3, and stops when it encounters 2 -> Right = 5 Since Left <= Right, if you change the two numbers, you get 2 1 6 3 4 5 7, and proceed again with Left = 1, Right = 4. Left starts at 1 and stops when it reaches 6 -> Left = 2 Right starts at 4 and stops when it reaches 3 -> Right = 3 Since Left <= Right, if you change the two numbers, you get 2 1 3 6 4 5 7, and proceed again with Left = 3, Right = 2. Left > Right -> Start < Right, Left < End Randomly call quickSort(0,2), quickSort(3,6) quickSort(0,2) => Start = 0, End = 2, pivot = arr[ (0 + 2) / 2] = arr[ 1 ] = 1 Left starts at 0 and stops when it reaches 2 -> Left = 0 Right starts at 2 and stops when it reaches 1 -> Right = 1 Since Left <= Right, if you change the two numbers, you get 1 2 3 6 4 5 7, and proceed again from Left = 1, Right = 0. Left > Right -> Start = Right, Left < End, so only quickSort(1,2) is called quickSort(1,2) = > Start = 1, End = 2, pivot = arr[ (1 + 2) / 2 ] = arr [ 1 ] = 2 Left starts at 1 and stops when it reaches 2 -> Left = 1 Right starts at 2 and stops when it reaches 2 -> Right = 1 Since Left <= Right, if you change the two numbers, you get 1 2 3 6 4 5 7, and proceed again with Left = 2, Right = 0. Left > Right -> Start > Right, Left = End so no more calls If you look at the result at this time, it is 1 2 3 6 4 5 7, and you can see that it is sorted from index 0 to 2. Likewise, if you proceed as follows for indices 3 to 6, all indices 0 to 6 will be sorted.

Explanations for All the Sorts

Bubble Sort

The bubble sorting algorithm is an algorithm that compares two consecutive elements of a list. If the two elements (example numbers) are in the right order, nothing needs to be changed. If the numbers are not in the right order, however, they will then be swapped so that the smaller numbers can be “bubbled” to the top of the list.

Bubble sort gets the job done of sorting the list; however, it does have an average time complexity of O(n^2), meaning that the number of operations performed will get larger and larger as the list in question gets larger and larger. Thus, even though bubble sort is one of the more simpler algorithms to understand, it may not be the best option when it comes to sorting.

Quick Sort

Quick sort selects one element of a list as a pivot. The list is then rearranged so that all elements less than the pivot come before it, while all elements greater than the pivot come after it. This process guarantees that the pivot element is in its correct position in the sorted list. Quick sort then recursively applies the same logic to the list of elements before the pivot and the list of elements after the pivot until the entire list is sorted.

Quick sort has an average time complexity of O(n log n), similar to merge sort. However, its worst-case performance is O(n^2), which occurs when the list is already nearly sorted or when the smallest or largest element is always chosen as the pivot.

Merge Sort

With the merge sorting algorithm, the algorithm takes one array and splits it in half. For each half of the array, the algorithm rearranges the array so that the elements are in the desired order. Once that has been done successfully, the algorithm merges the two arrays/lists back together so that the desired order is achieved for the entire array/list.

Merge sort, just like bubble sort, is also another way of sorting a list back into the desired order. However, merge sort is better than bubble sort in terms of time complexity, with merge sort having an average time complexity of O(nlogn). This means that the amount of operations performed will not be as large as the input size increases for a merge sort algorithm as it would be for a bubble sorting algorithm.

Insertion Sort

Insertion sort builds the final sorted list one item at a time. It removes one element per iteration and finds the location it belongs within the sorted part of the list, inserting it there. This process repeats until no unsorted elements remain.

Even though insertion sort has an average and worst-case time complexity of O(n^2), making it less efficient for large lists, it has several advantages. It is adaptive, meaning that its efficiency increases if the list is already partially sorted, and it is stable, keeping identical elements in the same order as they appear in the input.

Selection Sort

Selection sort divides the list into two parts: the sorted part at the start and the unsorted part at the rest of the list. Initially, the sorted part is empty, and the unsorted part contains all the elements. With each iteration, the algorithm selects the minimum (or maximum, depending on sorting order) element from the unsorted part and moves it to the end of the sorted part. This process is repeated until the unsorted part becomes empty, and the list is sorted.

Selection sort has a time complexity of O(n^2), making it inefficient for large lists. The primary advantage of selection sort lies in its simplicity and the fact that it makes the minimum possible number of swaps: only one swap for each element in the list, which could be beneficial in scenarios where writing data is significantly more expensive than reading data.