This week's assigned topic is about sorting and their efficiency and performance. To start off this post: How do we measure the efficiency of a sorting algorithm?
From what I learned, in order to measure the efficiency of a sorting algorithm, we need analyze the running time (or the number of steps) it takes for the algorithm to sort an input relative to the input's size. We do not measure the actual speed or amount of time it takes, as this can vary greatly for different computers, and instead we use Big Oh notation. This allows us to describe the performance of an algorithm in terms of the input size and allows us to know how the algorithm's performance changes as the input size changes.
There are many different complexities for Big Oh notation which can range from constant time O(1), to linear O(n), to quadratic O(n^2), to exponential O(2^n), or even factorial O(n!). In order to find the complexity for different sorting algorithm, we have to consider the number of comparisons, swaps, insertions, splits, etc. that the sorting algorithm performs on the list of elements relative to its size.
For sorting algorithms, we learned that a sort can have varying running times for the best, average and worst cases of the sort. For example, an insertion sort can have a linear running time O(n) in the best case, when used on an input that is already sorted, however it will have a quadratic running time O(n^2) in the worst case, when used on an input that is sorted in reverse.
In this course, we mostly focused on the worst case running times for sorts because this gives us an upper bound to the performance of a sorting algorithm and also allows us to compare sorting algorithms to one another.
