Enhancing Worst Sorting Algorithms

Abstract

Sorting is a commonly used operation in computer science. In addition to its main job, sorting is often required to facilitate some other operation such as searching, merging and normalization. There are many sorting algorithm that are being used in practical life as well as in computation. A sorting algorithm consists of comparison, swap, and assignment operations. Bubble sort, selection sort and insertion sort are algorithms which are easy to comprehend but have the worst time complexity of O(n2). In this paper enhancement of the selection sort and the bubble sort by eliminating some useless comparisons is presented. A stack is used to store the locations of the past or local maximums, which can be used in later iterations of these algorithms. The insertion sort is improved by reducing shift operations with the aid of a double sized temporary array. The new algorithms are discussed, analyzed, tested and executed for benchmarking along with representing results. A significant improvement of well above 200% is achieved.