Journal Press India^®

Author Details ( * ) denotes Corresponding author

Searching and Sorting are the most important data structure operations, which make easy searching, arranging and locating the information. One of the basic problems of computer science is sorting a list of items and searching elements in the array. There are a number of solutions to these problems, known as sorting algorithm, and searching algorithm. Some searching algorithms are simple and spontaneous, such as the Linear Search, Binary Search. All searching algorithms are problem specific meaning they work well on some specific problem and do not work well for all the problems, therefore, appropriate for specific kinds of problems. Some searching algorithm works on less number of elements. There are some fundamental sorting algorithms as Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Bubble Sort etc. After studying various sorting and searching algorithms we found that the algorithms can be optimised. This paper presents a new searching algorithms named as “OBSwQS” is designed to perform searching quickly and more effectively as compared to the existing version of searching algorithm in which there are used the concepts of Binary Search and Quick Sort algorithms, and the optimised sorting algorithms as “DNSS”, “DNBS”, “Insertion Sort within the Merge Sort” and etc. are the optimised sorting algorithm which are the optimization of Fundamental Selection Sort, Bubble Sort, Merge Sort and etc. The introduction of Dual Nature Selection Sort and Dual Nature Bubble Sort version of selection sort algorithm and Bubble Sort for sorting the data stored in database instead of existing selection sort algorithm and Bubble Sort algorithm will provide an opportunity to the users to save almost 50% of their operation time with almost 100% accuracy. In “Insertion Sort within the Merge Sort algorithm” there is found out the value of maximum value of n ( n is number of items to be sorted) so that the insertion sort beats the merge sort. Hence the “ISwMS” is optimization of Fundamental Merge Sort algorithm.

Keywords

Dual Nature Selection Sort; Dual Nature Bubble Sort; Insertion Sort within the Merge Sort Algorithm; Optimized Binary Search with Quick Sort

1. Y. Han, Deterministic sorting in O(nlog log n) time and linear space, Proceedings ofthe thirty-fourth annual ACM symposium on Theory of computing, Montreal, Quebec Canada, 2002, 602-608


2. M. Thorup, Randomized Sorting in O (n log log n) Time and Linear Space UsingAddition, Shift, and Bit-wise Boolean Operations, Journal of Algorithms, 42(2), 2002, 205-230


3. Y. Han, M. Thorup, Integer Sorting in O(n (log log n) Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, 135-144


4. P. M. McIlroy, K. Bostic, M. D. McIlroy, Engineering radix sort, Computing Systems, 2004, 224-230


5. M. D. McIlroy, A killer adversary for quick sort, Software--Practice andExperience,1999, 123-145


6. I. Flores, Analysis of Internal Computer Sorting, J.ACM 7, 4, 1960, 389- 409


7. G. Franceschini, V. Geffert, An In-Place Sorting with O (n log n) Comparisons and O (n) Moves, In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, 242-250, 2003


8. D. Knuth, The Art of Computer programming Sorting and Searching, 2nd edition, 3, Addison- Wesley, 1998


9. C. A. R. Hoare, Algorithm 64: Quick sort, Comm. ACM 4, 7, 1961, 321


10. Soubhik Chakraborty, Mausumi Bose, and Kumar Sushant, A Research thesis, On Why Parameters of Input Distributions need be taken into Account for a More Precise Evaluation of Complexity for Certain Algorithms


11. D.S. Malik, C++ Programming: Program Design Including Data Structures, Course Technology (Thomson Learning), 2002, www.course.com


12. D. Jim´enez-Gonz´alez, J. Navarro, and J. Larriba-Pey. CC-Radix: A Cache Conscious Sorting Based on Radix Sort, In Euromicro Conference on Parallel Distributed and Network based Processing, 101-108, 2003


13. J. L. Bentley, R. Sedgewick, Fast Algorithms for Sorting and Searching Strings", ACM-SIAM SODA, 97, 360-369, 1997


14. I. Flores, Analysis of Internal Computer Sorting, J.ACM 8, 1961, 41-80


15. J. W. J. Williams, Algorithm 232: Heap sort". Comm. ACM 7, 6, 1964, 347-348


16. A. Andersson, S. Nilsson, 1994, A New Efficient Radix Sort". In the Proceeding of the 35 Annual IEEE Symposium on Foundation of Computer Science, 1994, 714-721


17. I. J. DAVIS, A Fast Radix Sort, The computer journal 35, 6, 636-642, 1992


18. V. Estivill-Castro, D. Wood, A Survey of Adaptive Sorting Algorithms, Computing Surveys, 24:441-476, 1992


19. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, MA, 2, 2001