A Comparative Analysis of Deterministic Sorting Algorithms based on Runtime and Count of Various Operations
Reyha Verma and Jasbir Singh
Abstract
Sorting algorithms find its application in many practical fields of Computer Science. Efficient solving of sorting problem has attracted a great deal of research as it optimizes other algorithms also. The main factor which is taken into consideration while determining the efficiency of a sorting algorithm is the time complexity. Mostly the execution time of algorithms is investigated and compared for analyzing time complexity. This paper presents a comparative analysis of deterministic sorting algorithms. Time complexity of six different algorithms namely, Selection sort, Bubble sort, Insertion sort, Quicksort, Heapsort and Mergesort is determined in terms of number of comparisons, swaps and assignment operations in addition to average execution time. Also, the performance of these algorithms on fully and almost sorted lists was also analyzed. The study indicates that determining the operation’s count is essential for analyzing time complexity especially when algorithms are theoretically analyzed.
Keyword
Deterministic sorting, Time complexity, Bubble sort, Selection sort, Quicksort.