A New Sorting Algorithm with filling to the left and right

Year 2015, Volume: 3 Issue: 3, 135 - 141, 30.12.2015

Naiden Borisov Vasilev Atanaska Dimitrova Bosakova Ardenska

Abstract

This paper presents an algorithm for sorting by using of LIT (left inversions table). The algorithm is named LR. The time complexity of the proposed algorithm analytically evaluated. Two approaches for acceleration of LR are presented. The proposed algorithm and its two improvements are implemented in C++. Experimental comparisons are done between LR and some known algorithms, and between LR and its two modifications. The experiments show that LR is faster than “bubble sort” and “LtoRA” algorithms but it is slower than the algorithms “insertion sort” and “selection sort”. The experiments also show that for rows in which there is a large number of the repetitions, the modification “LR – repeat” is faster than the original algorithm, “Bubble sort”, “Selection sort” and the modification “LRA – minimax”. The algorithm “LR minimax” is faster than algorithm LR in all cases (when the row has large or small number of repetitions).

Keywords

Sorting algorithm, Left Inversions Table, Insertion sort, Selection sort

References

• [1] Knuth D., The art of computer programming, V3. Sorting and Searching, Addison Wesley Publishing Company, 1973. [2] Stoichev St., Synthesis and analysis of algorithms, BPS, Sofia, 2003 (in Bulgarian). [3] Nakov P., P. Dobrikov, Programming=++Algorithms, TopTeam Co, 2003 Наков (in Bulgarian). [4] Sedgewick R, Algorithms in C, Addison-Wesley, 1990. [5] Harris S., J. Ross, Beginning Algorithms, 2005. [6] Wirth N., Algorithms+data structures=programs, Prentice-Hall, 1976. [7] N. Vasilev, A. Bosakova-Ardenska, Algorithms for sorting by left inversions table, International Review on Computers and Software (IReCoS), vol 7 n2 – Part A, 2012, ISSN 1828-6003, pp 642-650.