Run-Time Analysis For Sorting Algorithms
Daniela Alexandra Crișan, Gabriel Florian Simion, Patrick Eugen Moraru · RePEc: Research Papers in Economics · 2015
Analysis of algorithms complexity is an issue that has always aroused great interest. This is because an algorithm, however 'smart' it may seem, it could require a huge execution time. There are analytic techniques of evaluating the complexity of an algorithm, although they usually are difficult to use. Most often, a more convenient solution is to estimate the run-time of the algorithm.In this paper, a run-time comparative analysis is presented. It consists in evaluating the run-times of three well-known sorting algorithms: QuickSort, BubbleSort and InsertSort. A thousand different arrays of different sizes were randomly generated for the tests. Two analyses have been done: the first computes the mean run-time using all 1000 arrays with different sizes, the second uses for 1000 times a single 1000 items array. The three algorithms were implemented in three most common programming languages: Java, C++ and C#. The empirical results show that the fastest sorting algorithm is Quicksort, followed by Insertsort, then by Bubblesort. This observation conforms to the theoretical time complexity. A comparison between the three programming languages shows that the implementation in Java obtained the shortest run-time, followed by the C++ and C# versions. The order was the same for all three sorting algorithm.