logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C++ Program to Implement Insertion Sort

Posted on July 29, 2013 by Manish

This is a C++ program to sort the given data using Insertion Sort.

Problem Description

1. Insertion sort algorithm sort data by inserting them one by one into the list.
2. The time complexity of this algorithm is O(n^2).

Problem Solution

1. This algorithm is based on sorting playing cards by picking and inserting them one by one.
2. Here we take data element and place it in sorted list.
3. It should be placed so that list remains sorted.
4. Display the result.
5. Exit.

advertisement
Program/Source Code

C++ program to implement Insertion Sort using linked lists.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include <iostream>
 
using namespace std;
 
// A structure to represent a node.
struct list
{
	int data;
	list *next;
};
 
// Function implementing insertion sort.
list* InsertinList(list *head, int n)
{
	// Creating newnode and temp node.
	list *newnode = new list;
	list *temp = new list;
 
	// Using newnode as the node to be inserted in the list.
	newnode->data = n;
	newnode->next = NULL;
 
	// If head is null then assign new node to head.
	if(head == NULL)
	{
		head = newnode;
		return head;
	}
	else
	{
		temp = head;
 
		// If newnode->data is lesser than head->data, then insert newnode before head.
		if(newnode->data < head->data)
		{
			newnode->next = head;
			head = newnode;
			return head;
		}
 
		// Traverse the list till we get value more than newnode->data.
		while(temp->next != NULL)
		{
			if(newnode->data < (temp->next)->data)
				break;
 
			temp=temp->next;
		}
 
		// Insert newnode after temp.
		newnode->next = temp->next;
		temp->next = newnode;
		return head;
	}	
}	
 
int main()
{
	int n, i, num;
	// Declaring head of the linked list.
	list *head = new list;
	head = NULL;
 
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>num;
		// Inserting num in the list.
		head = InsertinList(head, num);
	}
 
	// Display the sorted data.
	cout<<"\nSorted Data ";
	while(head != NULL)
	{
		cout<<"->"<<head->data;
		head = head->next;
	}
 
	return 0;
}
Program Explanation

1. Create a head node of the list structure.
2. Take input of data and simultaneously insert it into a list using InsertinList().
3. Assign the new element as newnode.
4. If the head is null then assign newnode to head.
5. Otherwise, insert the newnode so that list remains sorted.
6. Return head to main.
7. Display the result.
8. Exit.

advertisement
Runtime Test Cases
Case 1:(average case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 998
Enter element 2: 451
Enter element 3: 2
Enter element 4: 35
Enter element 5: 1206
 
Sorted Data ->2->35->451->998->1206
 
 
Case 2:(best case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 99845
Enter element 2: 564
Enter element 3: 332
Enter element 4: 86
Enter element 5: 1
 
Sorted Data ->1->86->332->564->99845
 
 
case 3: (worst case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 2
Enter element 2: 332
Enter element 3: 456
Enter element 4: 1024
Enter element 5: 16565
 
Sorted Data ->2->332->456->1024->16565

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

« Prev Page - C++ Program to Implement Merge Sort
» Next Page - C++ Program to Implement Heap Sort

« C++ Program to Implement Merge Sort
C++ Program to Implement Heap Sort »

Deep Dive @ Sanfoundry:

  1. C Programming Examples on Computational Geometry Problems & Algorithms
  2. C Programming Examples on Trees
  3. C Programming Examples using Recursion
  4. C Programming Examples on Arrays
  5. C Programming Examples on Graph Problems & Algorithms
  6. C++ Programming Examples on Combinatorial Problems & Algorithms
  7. C Programming Examples on Combinatorial Problems & Algorithms
  8. Java Programming Examples on Combinatorial Problems & Algorithms
  9. C Programming Examples on Searching and Sorting
  10. C# Programming Examples on Sorting
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.