---
marp: true
title: 23 April 2021
theme: default
paginate: true

---

# <!-- fit --> CS 199 EMP

### Hosted by Jackie Chan and Akhila Ashokan

**Topics:** Sorting Algorithms

---

# Resources

Sort tiebreakers objects, implement comparable.

Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/

Slides are on the course site!
https://cs199emp.netlify.app/

---

# "What have we covered already?"

We've been exposed to *four* sorting algorithms. Soon that number will be five with *insertion sort* on Monday, but these are the four algorithms.

- **Bubble Sort:** Think about values bubbling up to the top.

- **Insertion Sort:** Think about having an already sorted list and inserting new values into it.

- **Merge Sort:** Recursive algorithm (technically all could be recursive, but I think this one is well suit), takes advantage of the fact that *merging* two already sorted list is easy.

- **Quicksort:** Uses pivots and partitions to split the array apart into smaller pieces.

---

# "Any initial questions about these algorithms?"

Again, here they are: *bubble sort, insertion sort, merge sort, and quicksort*.

Some components (beyond the implementation details) that you should keep in mind for the quiz:

- **Runtime,** i.e. how fast does it finish?

- **Space/Memory Required,** i.e. how much space does this algorithm need to run?

- **Best/Worse Case,** i.e. to make *X* algorithm fast/slow, what type of array should I give it?

To practice these, we'll do some questions before coding to warm us up.

---

# Runtime Analysis and Why (10 minutes)

For each of the algorithms, give me the runtime (worse case):

**Question:** What's the runtime for *X* and why? Talk about the component/subroutine that contributes the most to its runtime.

*X* algorithm: (1) bubble sort, (2) insertion sort, (3) merge sort, (4) quicksort.

---

# Adversarial Examples (10 minutes)

Your job is to construct arrays (arbitrary, but say with *10* elements) for bubble sort, insertion sort, merge sort, and quicksort that will make it very slow. With quicksort, the pivot value will be the first element in the array/subarray.

Here's a place to get started. Given a sorted array, which of these algorithms will perform poorly?

```java
int[] arr = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

int[] bubbleSorted = bubbleSort(arr);
int[] insertionSorted = insertionSort(arr);
int[] mergeSorted = mergeSort(arr);
int[] quickSorted = quickSort(arr);
```

---

# Sort By Multiple Attributes (10 minutes)

Say you're a car company and need line up cars on your lot. A good way to do that would be sorting by *brand* and within those brands, sort by *color* so they look nice. We can do that alphabetically.

Instead of writing our own sorting algorithm, we'll use Java's built-in one and implement a Comparable interface for our cars.

Remember that `String` has a `.compareTo()` method that takes another string.

```java
System.out.println("Jackie".compareTo("Akhila")); // prints a positive number, >
System.out.println("apple".compareTo("banana"));  // prints a negative number, <
System.out.println("cats".compareTo("cats"));     // prints zero, ==
```

---

# Sort By Multiple Attributes Starter Code

```java
import java.util.Arrays;

public class Car implements Comparable<Car> {
  public String brand;
  public String color;
  
  public Car(String setBrand, String setColor) {
    this.brand = setBrand;
    this.color = setColor;
  }
  
  @Override
  public String toString() {
    return "(" + this.brand + ", " + this.color + ")";
  }
  
  @Override
  public int compareTo(Car c) {
    // Your code here.
  }
}

Car[] carLot = new Car[]{
    new Car("Toyota", "Silver"),
    new Car("Suburu", "Red"),
    new Car("Ford", "Red"),
    new Car("Nissan", "White"),
    new Car("Nissan", "Blue"),
    new Car("Ford", "Black")
};

Arrays.sort(carLot);

System.out.println(Arrays.toString(carLot));
```

---

# For Fun, My Favorite Sorting Algorithm (10 minutes)

BogoSort! Here's the pseudocode for it.

```java
List<Integer> bogoSort(List<Integer> ls) {
  // Is it sorted?
    // If no, shuffle and repeat.
    // If yes, return array.
}
```

I'll give you some code that does some of this, your job is to implement it and tell me how many elements it can sort before it times out!

---

# BogoSort Starter Code

```java
import java.util.List;
import java.util.Arrays;
import java.util.Collections;

List<Integer> bogoSort(List<Integer> ls) {
  // Your code here.
  // You probably want to take a look at: Collections.shuffle() documentation.
}

boolean isSorted(List<Integer> ls) {
  // Your code here.
}

List<Integer> ls = Arrays.asList(new Integer[]{3, 2, 1});

System.out.println(ls);
System.out.println(bogoSort(ls));
```

---

# That's all folks!

Another week finished, another week closer to summer break! As always hang in there (more saying that for myself, but you too)!

Now that you know some sorting algorithms, you can sort yourself out before finals! I surely need to do that.

---

# Solution Section

---

# Worse Case Runtimes and Justifications Solutions

1. Bubble sort has $O(n^2)$ runtime because each of the $n$ elements could bubble up the array at least $n-1$ times which is $n(n-1) = O(n^2)$. The bubbling up/swapping processing for each element is causing the runtime to be this way.

2. Insertion sort has $O(n^2)$ runtime because for an array with $n$ elemetns and at any particular index $i$, the number of swaps $n_i$ needs to make is $i-1$. The range of $i$ depends on $n$ so worse case scenario, the run time is $O(n^2)$ because $n$ elements need to be swapped $n$ times at most (rounding up $i$ swaps). 

---

# Worse Case Runtimes and Justifications Solutions Cont.

3. Merge sort has to split the array $log(n)$ times and the number of operations it performs can just be thought of as $n$ because it depends on $n$. Therefore, the runtime for merge sort is $O(nlog(n))$.

4. If you pick a particularly bad pivot with quicksort, then the list will not be split. It will have to pick $n$ pivots and do $n$ operations and have a total runtime of $O(n^2)$.

---

# Adversarial Examples Solutions

1. For bubble sort, the adversarial example would be passing in a reversed sorted list because it'll take more time for each of those elements to bubble to their correct position.

2. For insertion sort, exactly the same as bubble sort.

3. For merge sort, it doesn't matter because merge sort doesn't care.

4. For quicksort, depends on the pivot selection, but if the pivot is always the first element, then an already sorted list will cause it to hit the worse case runtime.

---

# Sort By Multiple Attributes Solution

```java
@Override
public int compareTo(Car c) {
  if (this.brand.compareTo(c.brand) == 0) {
    return this.color.compareTo(c.color);
  } else {
    return this.brand.compareTo(c.brand);
  }
}
```

---

# BogoSort Solution

```java
import java.util.List;
import java.util.Arrays;
import java.util.Collections;

List<Integer> bogoSort(List<Integer> ls) {
  while (!isSorted(ls)) {
    Collections.shuffle(ls);
  }
  
  return ls;
}

boolean isSorted(List<Integer> ls) {
  for (int i = 1; i < ls.size(); i++) {
    if (ls.get(i - 1) > ls.get(i)) {
      return false;
    }
  }
  
  return true;
}

List<Integer> ls = Arrays.asList(new Integer[]{3, 2, 1});

System.out.println(ls);
System.out.println(bogoSort(ls));
```