Our sort

Our sort is the selection sort in which we will be enacting a skit that will show how selection sort works

Dev.to

Here is a code chunk taken directly from a link provided by Mr. Mortensen done to Dev.to. This code has been done in python and I also try to recreate in Java so that I can get it on our sorting project. Also from this website, is a gif of how the selection sort is supposed to work which helps to realize how it should be done.

Selection Sort

data = [3, 1, 2, 0, 4, 5]

def selectionSort(data):
    for scanIndex in range(len(data)):
        minIndex = scanIndex

        for compIndex in range(scanIndex + 1, len(data)):
            if data[compIndex] < data[minIndex]:
                minIndex = compIndex

        if minIndex != scanIndex:
            data[scanIndex], data[minIndex] = data[minIndex], data[scanIndex]

    return data

data = [0, 1, 2, 3, 4, 5]
sorted_data = selectionSort(data)
print(sorted_data)

[0, 1, 2, 3, 4, 5]

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] data) {
        for (int scanIndex = 0; scanIndex < data.length; scanIndex++) {
            int minIndex = scanIndex;

            for (int compIndex = scanIndex + 1; compIndex < data.length; compIndex++) {
                if (data[compIndex] < data[minIndex]) {
                    minIndex = compIndex;
                }
            }

            if (minIndex != scanIndex) {
                int temp = data[scanIndex];
                data[scanIndex] = data[minIndex];
                data[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {3, 1, 2, 0, 4, 5};
        selectionSort(data);
        System.out.println(Arrays.toString(data));
    }
}
SelectionSort.main(null)

Other Sorts

There are 7 other sorts that were included within the blog from Dev.to, some of the other 4 teams will cover these other sorts, while there are some that won’t be shown in algorhythmic performances but will be seen in the blogs of students

Bubble Sort

data = [5, 4, 3, 2, 1, 0]

def bubbleSort(data):
    length = len(data)

    for iIndex in range(length):
        swapped = False

        for jIndex in range(0, length - iIndex - 1):

            if data[jIndex] > data[jIndex + 1]:
                data[jIndex], data[jIndex + 1] = data[jIndex + 1], data[jIndex]
                swapped = True

        if not swapped:
            break

    return data

sorted_data = bubbleSort(data)
print(sorted_data)

[0, 1, 2, 3, 4, 5]

Insertion Sort

data = [5, 4, 3, 2, 1, 0]

def insertionSort(data):
    for scanIndex in range(1, len(data)):
        tmp = data[scanIndex]
        minIndex = scanIndex

        while minIndex > 0 and tmp < data[minIndex - 1]:
            data[minIndex] = data[minIndex - 1]
            minIndex -= 1

        data[minIndex] = tmp

    return data

sorted_data = insertionSort(data)
print(sorted_data)

[0, 1, 2, 3, 4, 5]

Quick Sort

data = [5, 4, 3, 2, 1, 0]

def quickSort(data, left, right):
    if right <= left:
        return 
    else:
        pivot = partition(data, left, right)
        quickSort(data, left, pivot - 1)
        quickSort(data, pivot + 1, right)

    return data

def partition(data, left, right):
    """This function chooses a pivot point that determines the left and right side of the sort"""
    pivot = data[left]
    leftIndex = left + 1
    rightIndex = right

    while True:
        while leftIndex <= rightIndex and data[leftIndex] <= pivot:
            leftIndex += 1
        while rightIndex >= leftIndex and data[rightIndex] >= pivot:
            rightIndex -= 1
        if rightIndex <= leftIndex:
            break
        data[leftIndex], data[rightIndex] = data[rightIndex], data[leftIndex]

    data[left], data[rightIndex] = data[rightIndex], data[left]

    return rightIndex

sorted_data = quickSort(data, 0, len(data) - 1)
print(sorted_data)

[0, 1, 2, 3, 4, 5]

Merge Sort

data = [5, 4, 3, 2, 1, 0]

def mergeSort(data):

    if len(data) < 2:
        return data

    middle = len(data) // 2

    left = mergeSort(data[:middle])
    right = mergeSort(data[middle:])

    merged = merge(left, right)
    return merged

def merge(left, right):

    if not len(left):
        return right

    if not len(right):
        return left

    result = []
    leftIndex = 0
    rightIndex = 0

    while leftIndex < len(left) and rightIndex < len(right):
        if left[leftIndex] < right[rightIndex]:
            result.append(left[leftIndex])
            leftIndex += 1
        else:
            result.append(right[rightIndex])
            rightIndex += 1

    result.extend(left[leftIndex:])
    result.extend(right[rightIndex:])

    return result

sorted_data = mergeSort(data)
print(sorted_data)

[0, 1, 2, 3, 4, 5]

Bucket Sort

This was a sort that I didn’t know existed and it was interesting to learn about this sort.

data = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]

def bucketSort(data):
    if not data:
        return data

    max_value = max(data)
    min_value = min(data)
    bucket_range = (max_value - min_value) / len(data) if len(data) > 1 else 1
    bucket = [[] for _ in range(len(data))]

    for value in data:
        index_bucket = min(int((value - min_value) / bucket_range), len(data) - 1)
        bucket[index_bucket].append(value)

    for sublist in bucket:
        sublist.sort()

    sorted_data = []
    for sublist in bucket:
        sorted_data.extend(sublist)

    return sorted_data

sorted_data = bucketSort(data)
print(sorted_data)

[0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]

Shell Sort

This was another sort that I didn’t know of, but based on the animated picture, it seems like it is similar to Selection Sort, but doesn’t start at the minimum

data = [12, 34, 54, 2, 3]

def shellSort(data):
    length = len(data)
    gap = length // 2

    while gap > 0:
        for iIndex in range(gap, length):
            temp = data[iIndex]
            jIndex = iIndex

            while jIndex >= gap and data[jIndex - gap] > temp:
                data[jIndex] = data[jIndex - gap]
                jIndex -= gap

            data[jIndex] = temp

        gap //= 2

    return data

sorted_data = shellSort(data)
print(sorted_data)

[2, 3, 12, 34, 54]

Heap Sort

Here is another sort that I don’t know much about, I think it might have to do something with the storing data in the heap

data = [12, 34, 54, 2, 3]

def createHeap(data, length, index):
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2

    if left < length and data[largest] < data[left]:
        largest = left

    if right < length and data[largest] < data[right]:
        largest = right

    if largest != index:
        data[index], data[largest] = data[largest], data[index]
        createHeap(data, length, largest)

def heapSort(data):
    length = len(data)

    for index in range(length // 2 - 1, -1, -1):
        createHeap(data, length, index)

    for index in range(length - 1, 0, -1):
        data[index], data[0] = data[0], data[index]
        createHeap(data, index, 0)

    return data

sorted_data = heapSort(data)
print(sorted_data)

[2, 3, 12, 34, 54]

Algorhythmic Reflection

Overall, this was quite the experience. For a lot of us, it was very different than what we were used to, but we still gained a lot from it. Our understanding of sorting algorithms strengthened and our collaboration skills were put on full display in being able to not only coordinate times to meet for rehearsals, but giving each other directing notes for acting. Each individual put in effort too, as we all had our lines completely memorized (how many other teams did that?)

public abstract class Collectable implements Comparable<Collectable> {
    public final String finalStr = "Collectable";
    private String type;

    public interface KeyTypes {
        String model();
    }

    protected abstract KeyTypes getKey();

    public String getFinal() {
        return finalStr;
    }

    public String getType() {
        return type;
    }

    public void setType(String type) {
        this.type = type;
    }
}

class Phone extends Collectable {
    public static KeyTypes key = KeyType.id;

    public static void setOrder(KeyTypes key) {
        Phone.key = key;
    }

    public enum KeyType implements KeyTypes {id, model, company, price}

    private final String model;
    private final String company;
    private final int price;

    Phone(String model, String company, int price) {
        this.setType("Phone");
        this.model = model;
        this.company = company;
        this.price = price;
    }

    public static Phone[] phones() {
        return new Phone[]{
                new Phone("Galaxy S24 Ultra", "Samsung", 1299),
                new Phone("iPhone 15 Pro Max", "Apple", 1299),
                new Phone("Pixel 8 Pro", "Google", 3),
                new Phone("Wing", "LG", 999),
                new Phone("Razr", "Motorola", 999),
        };
    }

    public static List<Phone> selectionSort(List<Phone> arr) {
        int len = arr.size();

        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (arr.get(i).compareTo(arr.get(j)) > 0) {
                    Phone temp = arr.get(i);
                    arr.set(i, arr.get(j));
                    arr.set(j, temp);
                }
            }
        }
        return arr;
    }

    @Override
    public String toString() {
        return "Phone{" +
                "model='" + model + '\'' +
                ", company='" + company + '\'' +
                ", price=" + price +
                '}';
    }

    public static void main(String[] args) {
        Phone[] objs = phones();
        List<Phone> phones = new ArrayList<>(Arrays.asList(objs));

        Phone.setOrder(KeyType.id);
        Phone.print(objs);

        Phone.setOrder(KeyType.model);
        phones = selectionSort(phones);
        for (Phone phone : phones)
            System.out.println(phone);
    }
}
Phone.main(null)

  Cell In[1], line 1
    public abstract class Collectable implements Comparable<Collectable> {
           ^
SyntaxError: invalid syntax