CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

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.