sorting is the basic operation in every application of computer science. The paper proposes two novel sorting algorithms based on the concept of traditional insertionsort (IS). Firstly, Brownian Motus insertionsort ...
详细信息
sorting is the basic operation in every application of computer science. The paper proposes two novel sorting algorithms based on the concept of traditional insertionsort (IS). Firstly, Brownian Motus insertionsort (BMIS) based on IS is proposed. It is followed by Clustered binary insertion sort (CBIS) based on the principles of binary insertion sort (BIS). BIS is a binary search enhancement of IS which is a quite famous variant of it. Average case time complexity of BMIS is 0((0.54)root n);and that of CBIS is 0(n log n). The scenario which results into the worst case of IS is with the complexity of 0(n(2));and BIS with 0(n log n) is the best case scenario for BMIS and CBIS with complexity of 0(n). The probability of getting a worst case scenario for BMIS and CBIS is approximately zero. Comparison of proposed algorithms with IS and BIS has been performed at 25%, 50%, 75% and 100% level of randomness in the initial dataset. These results lead to prove our claim of devising efficient enhancements of IS. The results further reveal that performance of BMIS and CBIS will increase with a decrease in randomness level of the dataset in comparison to its counterparts. The number of comparisons required by BMIS and CBIS will approach to 0(n) with randomness level approach to zero. So, for nearly sorted datasets, our proposed BMIS and CBIS are the best choice. Both BMIS and CBIS are in-place, stable and online sorting algorithm. (C) 2018 Elsevier B.V. All rights reserved.
Lakshmanan, Ravikumar, and Ganesan (1991) studied the following problem of sorting a given set X = {x subscript 1, x subscript 2,..., x subscript n} of n distinct elements using binary comparisons of the form "Is...
详细信息
Lakshmanan, Ravikumar, and Ganesan (1991) studied the following problem of sorting a given set X = {x subscript 1, x subscript 2,..., x subscript n} of n distinct elements using binary comparisons of the form "Is x subscript i less than x subscript j," with 2 possible outcomes, "yes" and "no" for each comparison. However, some of the responses received for the comparisons could be erroneous. Intuitively, it is clear that, if there are no constraints on the errors, then the set cannot be sorted. Thus, it is assumed that the number of errors can be at most e, and e is known ahead of time. An algorithm is presented that requires at most O(n log n + en + e squared) comparison queries. That is, it matches the lower bound established by Lakshmanan, Ravikumar, and Ganesan for all values of e.
In this correspondence, we study the problem of sorting n distinct elements in ascending sequence according to a total order, using comparison queries which receive "yes" or "no" answers, but as ma...
详细信息
In this correspondence, we study the problem of sorting n distinct elements in ascending sequence according to a total order, using comparison queries which receive "yes" or "no" answers, but as many as e of which may be erroneous. In a half-lie version, all "yes" answers are guaranteed to be correct and the errors are confined to "no" answers. We show that the comparison query complexity of the sorting problem for this case is OMEGA (n log n + e) and then demonstrate an asymptotically optimal algorithm. In a full-lie version, however, both "yes" and "no" answers can be false. We show that the comparison query complexity of the sorting problem for this case is OMEGA(n log n + en) and then demonstrate an algorithm which generalizes the familiar binary insertion sort technique. This algorithm is asymptotically optimal if e = O(n).
暂无评论