Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Insertion Sort

By Exforsys | on September 9, 2011 |
C Algorithms

Insertion sort is a simple comparison sorting algorithm, that considers at a step k, the elements of the array A[0,k-1] are already sorted out, and the element on the k position will be inserted that way that after the insertion, the elements A[0,k] are sorted out.

Inserting the k element in the A[0,k-1] sequence requires a few steps:

  • the element must be retained in a temporal variable;
  • moving all the elements from the A[0,k-1] array that are greater than A[k] with a position to the right (this presumes a run from right to left of the array);
  • placing the A[k] element on the former spot of the last element that moved.

Step by step example :

Having the following list, let’s try to use insertion sort to arrange the numbers from lowest to greatest:

Unsorted list: 6 4 5 10 3 1 8 9 7 2

Step 1:

4 6 5 10 3 1 8 9 7 2 – As 6 was the first element, at step 1, the element 4 is being inserted, and 4 is smaller than 6, so it must place before 6, so the order would be 4 6.

Step 2:

4 5 6 10 3 1 8 9 7 2 – At step 2, 5 was the element to be inserted, and being smaller than 6, it goes before it, but then it is compared to 4 which is smaller than 5, now the order would be 4 5 6.

Step 3:

4 5 6 10 3 1 8 9 7 2 – At step 3, 10 was the new element, and being greater than 6, the element was in the right place and no moving had to take place, now the order would be 4 5 6 .

Step 4:

3 4 5 6 10 1 8 9 7 2 – At step 4, 3 was the new element, and compared to 10 it is smaller, so it has to move to the left, also, it is compared to 6 then to 5 and then to 4, and is smaller than any of these, so the position of the element 3 is at the left of all these numbers, now the order would be 3 4 5 6.

Step 5:

1 3 4 5 6 10 8 9 7 2 – Step 5, the new element is 1, which is again smaller than 10, then like in the previous steps, it is compared to the next numbers 6,5,4,3 and is smaller than an of these, so it ends at the left of the array that has been sorted out so far, with the order being 1 3 4 5 6

Step 6:

1 3 4 5 6 8 10 9 7 2 – At step 6, the element 8 was compared to 10 and moved to the left, but compared to 6 it is greater, so now the list would look like 1 3 4 5 6 8

Step 7:

1 3 4 5 6 8 9 10 7 2 – Step 7, the element 9 was compared to 10 and moved to the left having it being smaller, but it is greater than 8 so the list is : 1 3 4 5 6 8 9

Step 8:

1 3 4 5 6 7 8 9 10 2 – Step 8, the element of 7 was compared to 10, so it had to move to the left of 10, also 7 is smaller than 8 which it moves another position to the left, but it is greater than 6, so it found its position, with the array looking like : 1 3 4 5 6 7 8 9

Step 9:

1 2 3 4 5 6 7 8 9 10 – At the final step 9, the element 2 was compared to 10, being smaller it moves to the left, then again it is compared to 9, then 8, 7, 6, 5, 4, 3 and is smaller than any of these numbers, so the right position is to the left, but being greater than 1, it’s at one position to the right of the element 1, now the final order is the right one : 1 2 3 4 5 6 7 8 9 10

Having no more elements to compare 10 to, the algorithm now knows that the list is sorted.

Sample code:

  1.  #include < iostream >
  2. using namespace std;
  3.  
  4. int main(void)
  5. {
  6. 	int i;
  7. 	long int A[100];
  8. 	long int n=100;
  9. 	cout << "Please insert the number of elements to be sorted: ";
  10. 	cin >> n;	// The total number of elements
  11. 	for(int i=0;i < n;i++)
  12. 	{
  13. 		cout << "Input " << i << " element: ";
  14. 		cin >> A[i]; // Adding the elements to the array
  15. 	}
  16. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  17. 	for(int i=0;i < n;i++)
  18. 	{
  19. 		cout << A[i] << " ";
  20. 	}
  21.  
  22. 	for (int k=1;k < n;k++)
  23. 	{
  24. 		int temp=A[k];	// the k element to be inserted is retained in a temporal variable, 
  25. 		i = k-1;		//at first it is the A[1] value, which is the second value of the array
  26. 		while (i >=0 && A[i] > temp)
  27. 		{
  28. 			A[i+1] = A[i];
  29. 			i = i-1;
  30. 		}
  31. 		A[i+1] = temp;
  32. 	}
  33. 	cout << "Sorted list:" << endl;	// Displaying the sorted array
  34. 	for(int i=0;i < n;i++)
  35. 	{
  36. 		cout << A[i] << " ";
  37. 	}
  38. 	return 0;
  39. }

Output:

Code explanation:

  1. for (int k=1;k < n;k++)
  2. 	{
  3. 		int temp=A[k];
  4. 		i = k-1;		
  5. 		while (i >=0 && A[i] > temp)
  6. 		{
  7. 			A[i+1] = A[i];
  8. 			i = i-1;
  9. 		}
  10. 		A[i+1] = temp;
  11. 	}

The temp variable retains the value to be inserted, which at the first run of the loop would be A[1], being the second value as A[0] is the first value. Then the while loop checks to see if A[0] is greater than A[1], and if it is true, a swap between the values takes place. Also, i is decremented by 1. At the next run, A[2] is compared to A[1], and if it is greater a swap takes place, and after that it is compared to A[0], and if its greater there is a swap between the values, if not, the proper order has been found out.

Complexity:

How many compares are done? 1+2+…+(n-1) which results in O(n^2) worst case and (n-1)* 1 which is O(n) on best case. Also, how many element shifts are done? 1+2+…+(n-1) on O(n^2) worst case and 0 , O(1) best case.

Advantages:

  • it is easy to learn;
  • few lines of code;
  • efficient for small data sets;
  • stable, does not change the relative order of elements with equal keys;

Disadvantages:

  • not effective for large numbers of sorting elements;
  • needs a large number of element shifts;
  • as the number of elements increases the performance of the program would be slow.

Conclusion:

Like bubble sort, insertion sort is also a simple comparison algorithm. Unfortunately, it is not quite efficient on large lists, but it is an easy sorting algorithm to learn. The best case would be that the list was already sorted, meaning it would only have to traverse the list as oppose to traverse and swap. Worst case is achieved because regardless it has to traverse as well as swap through the entire list.

« « C Algorithms – Bubble Sort
C Algorithms – Shell Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 392 Followers
  • Popular
  • Recent
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Shell Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Radix Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – The Problem of Sorting the Elements

    September 8, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT