logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Brownian Motus and Clustered Binary Insertion Sort methods: An efficient progress over traditional methods

delete2018-09-01
delete10
PRE
AI
S
Shubham Goel
R
Ravinder Kumar *
DOI：10.1016/j.future.2018.04.038delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
Sorting is the basic operation in every application of computer science. The paper proposes two novel sorting algorithms based on the concept of traditional Insertion Sort (IS). Firstly, Brownian Motus Insertion Sort (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.
Keywords:
Brownian Motus insertion sort
Clustered Binary Insertion Sort
Insertion sort
Binary insertion sort
Sorting algorithm
Online algorithm
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

F
Future Generation Computer Systems-The International Journal of eScience
IF:
6.1
Papers:
6.8K
Citations:
2.3W

Organization

No organization information available