We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario

Published on October 2014 by Surabhi Patel, Moirangthem Dennis Singh, Chethan Sharma
journal_cover_thumbnail

International Conference on Information and Communication Technologies
Foundation of Computer Science USA
ICICT - Number 7
October 2014
Authors: Surabhi Patel, Moirangthem Dennis Singh, Chethan Sharma
be6cbb7d-ac18-43fb-8d8b-90a14a9a9177

Surabhi Patel, Moirangthem Dennis Singh, Chethan Sharma . Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario. International Conference on Information and Communication Technologies. ICICT, 7 (October 2014), 21-23.

@article{
author = { Surabhi Patel, Moirangthem Dennis Singh, Chethan Sharma },
title = { Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario },
journal = { International Conference on Information and Communication Technologies },
issue_date = { October 2014 },
volume = { ICICT },
number = { 7 },
month = { October },
year = { 2014 },
issn = 0975-8887,
pages = { 21-23 },
numpages = 3,
url = { /proceedings/icict/number7/18015-1476/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on Information and Communication Technologies
%A Surabhi Patel
%A Moirangthem Dennis Singh
%A Chethan Sharma
%T Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario
%J International Conference on Information and Communication Technologies
%@ 0975-8887
%V ICICT
%N 7
%P 21-23
%D 2014
%I International Journal of Computer Applications
Abstract

Insertion sort gives a time complexity of O(n) for the best case. In the worst case where the input is in the descending order fashion, the time complexity is O(n2). In the case of arrays, shifting takes O(n2) while in the case of linked lists comparison comes to O(n2). Here a new way of sorting for the worst case problem is proposed by using arrays as data structure and taking more space. 2n spaces is taken where n is the number of elements and starts the insertion from (n-1)th location of the array. In this proposed technique the time complexity is O(nlogn) as compared to O(n2) in the worst case.

References
  1. Insertion Sort,http://www. princeton. edu/~achaney/tmve/wiki100k/docs/Insertion_sort. html
  2. Wang Min, "Analysis on 2-Element Insertion Sort Algorithm", 2010 International Conference On Computer Design And Applications, IEEE Conference Publications, Pages 143-146 , 2010
  3. Thomas H. Cormen, Charles. E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms:Printice-Hall, Inc. , 2009
  4. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++: Pearson Addison-Wesley, 2006
  5. Michael A. Bender, "Insertion Sort is O(nlogn)," Third International Conference on Fun With Algorithms(FUN), Pages 16-23, 2004
  6. H. W. Thimbleby, "Using Sentinels in Insert Sort," SoftwarePractice and Experience, Volume 19(3), Pages 303–307,1989.
Index Terms

Computer Science
Information Sciences

Keywords

Insertion Sort Time Complexity Space Complexity.