UNIDIRECTIONAL TWO-WAY SORTING: THE IMPROVED WORST CASE PERFORMANCE OF O(N~2) SORTING ALGORITHMS

摘要

Choosing appropriate sorting algorithm in any programming language is an important issue. Several sorting algorithms have been suggested in the area of Data Structure design. Each algorithm has its own strengths and shortcomings. Therefore, providing an appropriate algorithm is too critical and may lead to an increase in performance. In order to clarify the suggested algorithm and improvements in this area, we conclude discussion with a summary on our evaluations. In this paper I developed a Unidirectional Two-Way sorting algorithm, which out beats all other O(n2) sorting algorithms like Bubble sort, Cocktail sort, Selection sort and Insertion sort for average and worst cases. We also give a time complexity analysis of the algorithm. Major limitation of the algorithm is that best case, average case and worst case behavior of the algorithm is same, that is there is no improvement in performance when the array is almost or already sorted.