Welcome to Lesson 21!Learning ObjectivesBy the end of this class, you should know...
(using last element as pivot) 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 + 11.5 Time Complexity of Quick Sort
2. Bucket Sort
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
Wrap Up
~ Have a Great Day! ~ |