Welcome to Lesson 21!

Learning Objectives

By the end of this class, you should know...
  • Quick Sort
  • Bucket sort

1. Quick Sort

  • Another Divide and Conquer algorithm
    • Pick a "pivot point". Picking a good pivot point can greatly affect the running time.
    • Break the list into two lists: those elements less than the pivot element, and those elements greater than the pivot element.
    • Recursively sort each of the smaller lists.
    • Make one big list: the 'smallers' list, the pivot points, and the 'biggers' list.


1.1. Quick Sort Performed on an Array

(using last element as pivot)


1.2. Quick Sort Partition Example


1.3. Quick Sort Pseudocode
Quicksort(A[], low, high) 
    if (low < high)
        pivot_location = Partition(A[],low,high) 
        Quicksort(A[], low, pivot_location - 1) 
        Quicksort(A[], pivot_location + 1, high) 

Partition(A[], p, r) 
    pivot = A[r] //choose largest value for pivot location 
    leftwall = p - 1
    for i = p to r - 1
        if A[i] < pivot //compare each value to the pivot
            leftwall++
            A[i] <---> A[leftwall] //swap
    A[r] <---> A[leftwall+1] //swap to put pivot in proper location
    return leftwall + 1

1.4. In-Depth Quick Sort Pseudocode Explanation (Highly Recommended!)



1.5 Time Complexity of Quick Sort
  • Best Case: O(n log n) 
  • Worst Case: O(n2)
  • Average Case: O(n log n)
  • In practice is faster than Merge Sort
  • Khan Academy Analysis of the Big-O run-time of Quicksort



2. Bucket Sort
  • No longer a comparison-based sorting algorithm
  • Instead a parallel sorting algorithm
  • Sort values into individual "buckets"
  • Re-arrange them within the bucket into a sorted order
  • Combine buckets back into array or list
  • Here we scatter (into buckets) and gather (back into the array) rather than divide and conquer
  • Mainly useful when input is uniformly distributed over a range


2.1. Visualizing Bucket Sort

Scatter elements into their respective bins

Sort elements inside of bins and return to the array

2.2. Bucket Sort In Under 40 Seconds
2.3. Bucket Sort Pseudocode

bucketSort(A[], k) //pass in k = number buckets
    List buckets[k] //an array of Lists or 2D array to be our buckets
    for i = 0 to array_size-1
        insert array[i] into buckets[correctBucket(array[i])]
    for i = 0 to k-1 //for all the buckets
        sort(buckets[i])//call sorting algorithm of choice
    return concat(buckets[0]...buckets[k-1])
    

2.4. Time Complexity of Bucket Sort
  • Best Case: O(n + k) //k = number of buckets
  • Worst Case: O(n2) //if all elements in one bucket and sort with slow sorting algorithm
  • Average Case: O(n + k)


Wrap Up
  • Answer the review questions for this lesson on Canvas

~ Have a Great Day! ~