Development of sorting and searching algorithms

The increase in the rate of data is much higher than the growth in the speed of computers, which results in a heavy emphasis on sort and search algorithms in the research literature. In this thesis, we propose a new efficient sorting algorithm based on the insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is an in-place sorting algorithm, and it has a remarkably efficient average case time complexity when compared with a standard insertion sort. By comparing our new algorithm with the QuickSort algorithm, BCIS shows faster average case times for relatively small arrays of up to 1500 elements. Furthermore, BCIS was observed to be faster than QuickSort within the high rate of duplicated elements even for large arrays. We present a hybrid algorithm to search ordered datasets based on the idea of interpolation and binary search. The presented algorithm is called Hybrid Search (HS), which is designed to work efficiently on unknown distributed ordered datasets. Experimental results showed that our proposed algorithm has better performance when compared with other algorithms that use a similar approach. Additionally, this study describes and analyses an unaddressed issue in the implementation of the binary search. In spite of this issue not affecting the correctness of the algorithm, it decreases its performance. However, the study presents a precise analytical approach to describe the behavior of the binary search in terms of comparisons number. With the help of this method, the complexity of the weak implementation is proved. Experimental results show that the weak implementation is slower than the correct implementation when a large sized search key is used. The presence of this implementation issue within other algorithms is also investigated. Finally, we present two efficient search algorithms, the first of which is an improved implementation of the ternary search, and the second a new algorithm called Binary-Quaternary search (BQ search). BQ search uses a new efficient divide-and-conquer technique. Both proposed algorithms, theoretically and experimentally, show better performance when compared with binary searches. Although the proposed BQ search displays a slightly higher average comparisons number than the improved ternary search, experimentally the BQ search shows better performance compared with improved ternary searches under some conditions.