In the latest period I decided to read again the amazing Cormen and co. — Introduction to Algorithms book and it threw me back to an age ago when I attended the University.
So I wanted to write this post for personal knowledge but also because there are a lot of question around the web like “What’s the fastest sorting algorithm?” or “How to write down the bubble sort” during the iOS interviews. So maybe this post could help you to prepare the next interview 🙂
The topics covered in this article are:
Big O Notation
The first topic to cover before learning about sorting algorithms is the concept behind the Big O Notation, or before this, the concept of asymptotic growth of an algorithm:
[…] That is, we are concerned with how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound. Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.
In this definition taken from the Cormen Book, there are two underlying concepts:
- this asymptotic growth is something we use to compare algorithms, so we can answer properly to questions like “What’s the fastest sorting algorithm?” comparing their asymptotic growth;
- it’s a measure of the performances of a target algorithm based on the input;
Using this definition we can completely skip any other formal definition, referring to the Big O notation considering these sentences:
- This step is O(1) –> this means that, regardless the input size, the considered step is constant;
- This cycle is O(N), where N is the input size –> this means that, the performance of this cycle is directly related to the input size; if a cycle is O(N) and another on the same input is O(N²) then the first cycle is faster than the second on the same input;
- If an algorithm is O(2*N) or O(N+N) we just say that it’s O(N)! The constants don’t have any value here!
Generally speaking we can refer to asymptotic growth in different scenarios but we usually refer to the worst case in time complexity: this is finally the Big O Notation we refer to! (Hint: The complexity could be expressed in terms of time or space)
Let’s now move to talk about the most famous sorting algorithms 🤓