import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.nio.file.Files;
import java.nio.file.Paths;

// Collectable class
class Collectable {
    // Bubble sort method for sorting by year
    // O
    public static <T extends Comparable<? super T>> void bubbleSort(ArrayList<T> 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) {
                    Collections.swap(list, j, j + 1);
                }
            }
        }
    }

    // Merge sort method for sorting by make
    public static <T extends Comparable<? super T>> void mergeSort(ArrayList<T> list) {
        if (list.size() > 1) {
            int mid = list.size() / 2;
            ArrayList<T> left = new ArrayList<>(list.subList(0, mid));
            ArrayList<T> right = new ArrayList<>(list.subList(mid, list.size()));

            mergeSort(left);
            mergeSort(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++));
            }
        }
    }

    // Selection sort method for sorting by price
    public static <T extends Comparable<? super T>> void selectionSort(ArrayList<T> 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;
                }
            }
            if (minIndex != i) {
                Collections.swap(list, i, minIndex);
            }
        }
    }

    // Insertion sort method for sorting by make
    public static <T extends Comparable<? super T>> void insertionSort(ArrayList<T> list) {
        int n = list.size();
        for (int i = 1; i < n; i++) {
            T 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);
        }
    }

    // Quick sort method for sorting by year 
    // 0(n log(n)) all cases
    public static <T extends Comparable<? super T>> void quickSort(ArrayList<T> list) {
        if (list.size() > 1) {
            int pivotIndex = list.size() / 2;
            T pivot = list.get(pivotIndex);

            ArrayList<T> left = new ArrayList<>();
            ArrayList<T> right = new ArrayList<>();

            for (int i = 0; i < list.size(); i++) {
                if (i == pivotIndex) continue;
                T current = list.get(i);
                if (current.compareTo(pivot) <= 0) {
                    left.add(current);
                } else {
                    right.add(current);
                }
            }

            quickSort(left);
            quickSort(right);

            list.clear();
            list.addAll(left);
            list.add(pivot);
            list.addAll(right);
        }
    }
}

// Car class implementing Comparable
class Car implements Comparable<Car> {
    private String make;
    private int year;
    private double price;

    public Car(String make, int year, double price) {
        this.make = make;
        this.year = year;
        this.price = price;
    }

    // CompareTo method for sorting by year
    @Override
    public int compareTo(Car otherCar) {
        return Integer.compare(this.year, otherCar.year);
    }

    // CompareTo method for sorting by make
    public int compareByMake(Car otherCar) {
        return this.make.compareTo(otherCar.make);
    }

    // ToString method
    @Override
    public String toString() {
        return "Car{" +
                "make='" + make + '\'' +
                ", year=" + year +
                ", price=" + price +
                '}';
    }
}

public class Main {

    private static List<String> readMakes() {
        try {
            List<String> lines = Files.readAllLines(Paths.get("./car_data.csv"));
    
            return lines;
        } catch (IOException e) {
            e.printStackTrace();
            return null;
        }
    }

    public static void main(String[] args) {
        ArrayList<Car> cars = new ArrayList<>();

        List<String> MAKES = readMakes();
        for (String make : MAKES) {
            int year = (int) (Math.random() * 30) + 1990; // Random year between 1990 and 2020
            double price = (Math.random() * 40000) + 10000; // Random price between $10,000 and $50,000
            cars.add(new Car(make, year, price));
        }
    
        int iterations = 5;
    
        long bubbleSortTotalTime = 0;
        long mergeSortTotalTime = 0;
        long selectionSortTotalTime = 0;
        long insertionSortTotalTime = 0;
        long quickSortTotalTime = 0;
    
        for (int i = 0; i < iterations; i++) {
            Collections.shuffle(cars);
    
            // Bubble sort
            long startTime = System.nanoTime();
            Collectable.bubbleSort(new ArrayList<>(cars));
            long endTime = System.nanoTime();
            bubbleSortTotalTime += (endTime - startTime);
    
            // Merge sort
            startTime = System.nanoTime();
            Collectable.mergeSort(new ArrayList<>(cars));
            endTime = System.nanoTime();
            mergeSortTotalTime += (endTime - startTime);
    
            // Selection sort
            startTime = System.nanoTime();
            Collectable.selectionSort(new ArrayList<>(cars));
            endTime = System.nanoTime();
            selectionSortTotalTime += (endTime - startTime);
    
            // Insertion sort
            startTime = System.nanoTime();
            Collectable.insertionSort(new ArrayList<>(cars));
            endTime = System.nanoTime();
            insertionSortTotalTime += (endTime - startTime);
    
            // Quick sort
            startTime = System.nanoTime();
            Collectable.quickSort(new ArrayList<>(cars));
            endTime = System.nanoTime();
            quickSortTotalTime += (endTime - startTime);
        }
    
        // Calculate average times for each sort
        long bubbleSortAverageTime = bubbleSortTotalTime / iterations;
        long mergeSortAverageTime = mergeSortTotalTime / iterations;
        long selectionSortAverageTime = selectionSortTotalTime / iterations;
        long insertionSortAverageTime = insertionSortTotalTime / iterations;
        long quickSortAverageTime = quickSortTotalTime / iterations;
    
        // Print average times
        System.out.println("Average Bubble Sort Time: " + bubbleSortAverageTime + " ns");
        System.out.println("Average Merge Sort Time: " + mergeSortAverageTime + " ns");
        System.out.println("Average Selection Sort Time: " + selectionSortAverageTime + " ns");
        System.out.println("Average Insertion Sort Time: " + insertionSortAverageTime + " ns");
        System.out.println("Average Quick Sort Time: " + quickSortAverageTime + " ns");
    }
}

Main.main(null);

Average Bubble Sort Time: 717628572 ns
Average Merge Sort Time: 8291578 ns
Average Selection Sort Time: 178710491 ns
Average Insertion Sort Time: 210890746 ns
Average Quick Sort Time: 55940164 ns

How Quick Sort Works

Choose a Pivot:
- Select a pivot element from the array. The pivot can be chosen in different ways, such as selecting the first element, the last element, or a random element.
```
int pivotIndex = list.size() / 2;
T pivot = list.get(pivotIndex);
```

Partitioning:

Rearrange the array elements in such a way that elements smaller than the pivot come before it, and elements greater than the pivot come after it. This process is called partitioning.

ArrayList<T> left = new ArrayList<>();
ArrayList<T> right = new ArrayList<>();

for (int i = 0; i < list.size(); i++) {
    if (i == pivotIndex) continue;
    T current = list.get(i);
    if (current.compareTo(pivot) <= 0) {
        left.add(current);
    } else {
        right.add(current);
    }
}

Recursion:
- Recursively apply the above steps to the sub-arrays created by partitioning until the entire array is sorted.
```
quickSort(left);
quickSort(right);
```
Combine:
- After sorting the sub-arrays, combine them with the pivot element to form the final sorted array.
```
list.clear();
list.addAll(left);
list.add(pivot);
list.addAll(right);
```
Base Case:
- The process terminates when the array size becomes 1 or less, as a single element array is already considered sorted.
```
if (list.size() <= 1) {
    return;
}
```

Our Script - Link

Al Capone (QuickSort) vs Bugs Moran (Bogo Sort)
I was Bugs Moran, it was fun acting out and directing my peers to do their job. Although I lead the bogo sort, I also participated in Quick Sort for practice and learned a lot alongside my peers

Feedback

Organized
Liked the display of 2 algorithms
Good projection
Good use of space

Other Scripts

Bubble Sort
- Rachit & his many mistresses
- I was engaged with and really enjoyed the concept of a dating show. Their performance was filled to the brim with not only information about how bubble sort works, but also with comedy and concision that allowed for ease of understanding.
Merge Sort
- Ethan & his DUNE Remake
- I also really liked this concept, i thought that the visuals of how everyone would split into their clusters was really powerful, and it allowed for me to understand the sort quite well.
Selection Sort
- Paraas & his goons
- First sort, was a little hard to understand initially. Once they got into the groove of things it was good
Insertion sort
- Raymond & his play
- The unique approach to this assignment gave me a sense of joy and aspiration to learn about sorting algorithms in new, exciting ways such as this.

Algorythmic!!! • 20 min read

Description

How Quick Sort Works

Our Script - Link

Feedback

Other Scripts