CSE 214 Lecture 33: Quicksort
5 Dec 2016
School
Department
Course
Professor
Document Summary
If the pivot falls in the beginning, it would be o(n) since it must compare with every single other element in the array. If the pivot falls in the middle, the list size keeps being divided by 2 similar to merge sort which would make o(logn). Assume the pivot ends up in the center position of the array. Then, quick sort runs in o(nlogn) time just like merge sort. It would end up taking n passes in order to compare all the elements. It would go from n-1, n-2, n-3, n-4 if the pivot started comparing from the end of the list to the beginning. Combined with the partitioning which is o(n) and then o(n) when the pivot is not in the beginning, it would be o(n^2) in total. Then we get two subarrays, one of size 0, and the other of size n-1 (instead of n/2) Quick sort performs this poorly when the list is already sorted.
