## 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 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...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! ~