I've started to look into sorting algorithms and I wonder how you calculate the performance.
Like bubble sort have a worst case performance on O(n^2) and best case on O(n).
How do you calculate this? What's the worst / best case for my algorithm?
I'm pretty new to sorting, so please send me some feedback or links if you have.
Posts: 142 Location: The Netherlands Joined: 23.02.08 Rank: Newbie
Posted on 26-06-10 14:13
Whether you end up with the best or worst case scenario, depends on the data you're sorting. In the case of bubble sort, you get a time complexity of O(n) when you're sorting an already completely sorted list.
To correctly measure different sorting algorithms, you should try this with multiple different lists, as it's hard to determine how sorted your data already is when it's not an extreme case. Then just let it sort the data like a couple of hundred of times and keep track of time by using the right functions. In C++ for example, include ctime and use time() before and after, and calculate the difference.