Welcome to Lesson 19! Learning Objectives By the end of this class, you should know...
Announcements
Sorting Algorithms
Sorting Algorithms
Bubble Sort Animation Bubble Sort Bubble Sort Pseudocode: BubbleSort(A[], size) for i = 0 to size  1 for j = 0 to size  1 if A[j] > A[j+1] A[j] <> A[j+1] //swap Advantage:
Merge Sort
Merge Sort Animation Merge Sort Pseudocode MergeSort(A[], low, high) if (low < high) middle = (low + high) / 2 //midpoint formula MergeSort(A[], low, middle) MergeSort(A[], middle+1, high) Merge(A[], low, middle, high) Merge(A[], low, mid, high) l = low m = mid + 1 index = low //current index of result array result[low...high] //will store sorted values while (l <= mid AND m <= high) //while both subarrays are non empty if(A[l] < A[m]) //A[l] is smaller value so copy into result result[index] = A[l] index++ l++ else result[index] = A[m] index++ m++ while (l <= mid) //right subarray is empty so copy over all of left side values result[index] = A[l] index++ l++ while (m <= high) //left subarray is empty so copy over all right side values result[index] = A[m] index++ m++ Copy(A, result) //copy contents of result into original Array A
Time Complexity of Merge Sort
Merge Sort with Cards Bucket Sort
Visualizing Bucket Sort Scatter elements into their respective bins Sort elements inside of bins and return to the array Bucket Sort In Under 40 Seconds 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_size1 insert array[i] into buckets[correctBucket(array[i])] for i = 0 to k1 //for all the buckets sort(buckets[i])//call sorting algorithm of choice return concat(buckets[0]...buckets[k1]) Time Complexity of Bucket Sort
Sorting Algorithm Race Quick Sort
Quick Sort Pseudocode Explanation Quick Sort Performed on an Array (using last element as pivot) Quicksort(A[], low, high) if (low < high) pivot_location = Partition(A[],low,high) Quicksort(A[], low, pivot_location) Quicksort(A[], pivot_location + 1, high) Partition(A[], low, high) pivot = A[high] //choose largest value for pivot location leftwall = low  1 //move leftwall around instead of pivot for i = low + 1 to high if A[i] < pivot //compare each value to the pivot leftwall++ A[i] <> A[leftwall] //swap A[low] <> A[leftwall+1] //swap to put pivot (A[low]) in proper location return leftwallTime Complexity of Quick Sort
Average Case Intuition: Suppose, we pick the pivot element at random in an array of n keys.. The pivot element is from positions 1/4n. to 3/4.n.. 11/4n3/4nn Thus, the larger remaining subarray contains at most
.3/4n.
elements.. What is the maximum number of partitions we
need to get from 3/4n elements down to 1 element.? (3/4)^{levels} * n = 1 n = (4/3)^{levels} log n = levels * log(4/3) levels = log n * (1/log(4/3)) levels < 2 log nWrap Up
Upcoming Assignments
