Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical i...

Full description

Saved in:
Bibliographic Details
Published in:Future generation computer systems 2017-06, Vol.71, p.102-112
Main Authors: Mohammed, Adnan Saher, Amrahov, Şahin Emrah, Çelebi, Fatih V.
Format: Article
Language:English
Subjects:
BCIS
Bidirectional insertion sort
Insertion sort
Quicksort
Sorting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array. •We propose a new efficient sorting algorithm Bidirectional Conditional Insertion Sort (BCIS).•We compare BCIS with insertion sort and quicksort.•We prove that the average time complexity of BCIS very close to O(n1.5) for normally or uniformly distributed data.
ISSN:0167-739X
1872-7115
DOI:10.1016/j.future.2017.01.034