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?

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.

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

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.

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

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(n2)O(n^2) runtime because each of the nn elements could bubble up the array at least n−1n-1 times which is n(n−1)=O(n2)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(n2)O(n^2) runtime because for an array with nn elemetns and at any particular index ii, the number of swaps nin_i needs to make is i−1i-1. The range of ii depends on nn so worse case scenario, the run time is O(n2)O(n^2) because nn elements need to be swapped nn times at most (rounding up ii swaps).

Worse Case Runtimes and Justifications Solutions Cont.

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

  2. If you pick a particularly bad pivot with quicksort, then the list will not be split. It will have to pick nn pivots and do nn operations and have a total runtime of O(n2)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

@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

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));