CMPT 225 Lecture Notes - Lecture 5: Sorting Algorithm, Simple Function, Insertion Sort

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

Amount of work doing is ~number of items in array (holds up better if the array is larger). How many times does n have to be divided in half before the result is 1? log2(n) times. Quicksort performs n*log2(n) operations in the best case. Worst case: pivot is smallest or largest value. Absolute worst is where this is basically every case -> doesn"t divide sub array in half at all, just finds correct place for one value at a time. Partitions either into smaller or larger values, not both. In this case, array has to be partitioned (roughly) n times (actually n-1) Worst case performance: around n^2 operations (or n-1 * n or something) Worst case usually occurs when array is nearly sorted in either direction. In this case, insertion sort would actually be extremely fast. Typically much more concerned about worst case than best case. For example, when you have very specific time requirements.