Run-Time Analysis For Sorting Algorithms

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.