# Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting. How can we determine the resultant running time for each of the above algorithms given {2,3,5,4,6} as an input?

• From what I understand, you require to find out the $exact$ running time of the execution of your program. In that case, it might be wiser to ask this question on StackOverflow. Also, I think it would depend upon the programming language, but a nice implementation in Python is through the "timeit" module, which you can learn about here: docs.python.org/3/library/timeit.html Here is a question with answers on StackOverflow about timeit: stackoverflow.com/questions/8220801/how-to-use-timeit-module Jun 25, 2021 at 2:10
• Alternatively, analyse the number of key comparisons and assignments to "the array". Jun 25, 2021 at 6:50
• yeah, that is what I thought and by the way, I am using c++. Apologies for not clarifying this. Jun 25, 2021 at 7:22

We analysis mentioned algorithms with assumption $$n\to \infty$$ that $$n$$ is input size. So for a small input or constant number of input, measuring the running time of those algorithms are not correct. For example maybe for a given input with small size, after analysis running time you get an equal complexity but in general some of those algorithm have huge difference in time complexity, and we can see it as $$n\to \infty$$. In-addition, each algorithm that you mentioned have a constant factor, consequently using some symbol such as $$O(.)$$ to represent the complexity of that algorithm hide that constant.

The running time is measured independently of a particular input, and it is always written in asymptotic form (big-O notation).

You can't know the exact time an algorithm will run, since there are a lot of unpredictable factors that contribute to it.

• There should be a way that tells roughly if a particular algorithm runs faster than another. I am not talking about complexity and large inputs here, rather I am talking about a specific and known input. Jun 24, 2021 at 12:52
• One solution would be to count the number of swap and comparison but if I remember correctly, then counting sort is not comparative. Jun 24, 2021 at 13:03

You can use <time.h> in C to precisely figure out how long your sorting program has run.

#include <time.h>

int main(){

clock_t start = clock();

sort(); // Whatever sorting algorithm of your choice

clock_t stop = clock();

float running_time = (float)(stop - start) / CLOCKS_PER_SEC;

return 0;

}


This might give you a rough estimate of how long your program has run, but with a 5 element array of 8-bit integers, you'll always get 0.00 in the running-time variable as it's not precise enough.

So, to find a more explicit answer, try to sort an array of 50,000 elements of 32-bit integers. This will give a clearer view of how each algorithm is performing.