EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Insertion Sort in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Insertion Sort in Data Structure

By Priya PedamkarPriya Pedamkar

Insertion Sort in Data Structure

Introduction to Insertion Sort in Data Structure

The following article provides an outline for Insertion Sort in Data Structure. Insertion sort essentially works as per its name. As the name goes, it basically inserts the element at its correct position by following a step-by-step process. This algorithm is straightforward to implement and also performs the sorting operation quickly. It should be noted that while there are many sorting algorithms, the use of one, such as the method of insertion, should be controlled by the nature of the data and other technical requirements.

Algorithm of Insertion Sort in Data Structure

The algorithm to implement insertion sort is as given below:

Go through each of the algorithm’s steps to understand how the working of the steps. Based on this algorithm, we shall implement the program for insertion sort.

Algorithm:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

function insertion sort(data_type array[], integer variable n)
begin
declare integer variable temporary
declare integer variables i, j
loop (i = 0, i < n, i++)
begin
temporary = array[i] j = i
until (j > 0 and temporary < array[j-1])
begin
a[j] = a[j-1] j = j – 1
end
a[j] = temporary
end
end

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,294 ratings)

Program to Implement Insertion Sort

We have implemented a program for insertion sort using C programming.

Go through the following code and see how each of the elements viz. statements, loops, variables, etc., work.

Code:

#include <stdio.h>
#include <conio.h>
void main()
{
int arr[50], num, i, j, pos, temp;
printf("Enter the number of elements in the array: ");
scanf("%d", &num);
printf("\nEnter the numbers: ");
for(i = 0; i < num; i++)
{
scanf("%d", &arr[i]);
}
for(i = 0; i < num; i++)
{
temp = arr[i];
j = i;
while(j > 0 && temp < arr[j-1])
{
arr[j] = arr[j-1];
j = j-1;
}
arr[j] = temp;
}
printf("\nThe array sorted in ascending order is as follows.\n");
for(i = 0; i < num; i++)
{
printf("%d ", arr[i]);
}
getch();
}

Explanation:

  • We tested the above-implemented program through a series of inputs. It is essential to test the program to validate that it works properly. When the program is executed, firstly, we are asked by the program to enter the desired number of elements in the array. Next, we should specify the numeric elements. Note that if we intend to have an array of three elements, then the array elements should be passed separated by space.
  • E.g. if we want to pass numbers 33, 98, and 76, the three elements then enter the input as 33 98 78 and not as 339878 otherwise, it will be considered a single input. Now, let’s go through the following three inputs and the results obtained to confirm that the program implementing the insertion sort algorithm is correct.

Input 1:

In this case, we kept the number of elements in the array to five and passed the elements shown in the following screenshot. The program has worked correctly, and we’re going to the sorted array as can be seen at the bottom of the screenshot.

Insertion Sort in Data Structure eg1

Input 2:

It is essential to validate a program through inputs of various types. In this case, we passed an array that has elements present in the descending order. As we can see in the screenshot, we passed eight elements all present in descending order. When the algorithm works, it gives us the correct result, i.e. array sorted in ascending order. So, it means the insertion sort program is working correctly.

Insertion Sort in Data Structure eg2

Input 3:

Here, we passed an array of size ten with elements that do not necessarily have the same number of digits. In the screenshot, there are one digits numbers right to four digits numbers in the array. But still, we got the array sorted in ascending order. Through various types of input, we have thus confirmed that the algorithm works correctly.

Insertion Sort in Data Structure eg3

How the Insertion Sort Algorithm Works

In the above section, we saw the algorithm and program in C programming language to implement the algorithm. However, it is important to understand how the sorting algorithm works. We shall now go through a step-by-step process to understand how the insertion sort algorithm works. For the demonstration, we will consider an array containing six elements. The array we are considering has elements 87, 34, 76, 37, 98, and 12 in that order. Let’s see how the insertion sort algorithm gives us an ascendingly sorted array.

Step 1: The algorithm works from the left-hand side. We have no element before 87, as it is the first element, so the array remains as shown below.

insert 1

Step 2: Now, from the left-hand side, 34 is the next element which is less than 87, and so the positions of these two numbers get swapped. The array now looks like as shown below.

insert 2

Step 3: The third element in the array is 76, which is less than 87 and is greater than 34, so it gets inserted between the two elements in the second position giving us the following array.

insert 3

Step 4: Now, the fourth element in the array is 37. Compared to the three elements in the left-hand side, this is greater than only 34, and so it comes at the second position, and the array becomes as shown below.

insert 4

Step 5: When we move to the fifth element from the left-hand side, which is 98, we find that it is greater than all the elements to its left, and the array remains as it was in the previous step.

insert 5

Step 6: Finally, the last element is 12, which should come in the first place. So, the array gets shifted and 12 come in the first place as can be seen below.

insert 6

Conclusion

Amongst many sorting algorithms, insertion sort is one that can be effectively used to sort the data. In data structures, algorithms have to be used based on the context, and insertion sort becomes handy when it comes to reducing the processing time.

Recommended Articles

This is a guide to Insertion Sort in Data Structure. Here we discuss the working, algorithm and different programs to implement insertion sort in the data structure. You may also look at the following articles to learn more –

  1. Arrays in Data Structure
  2. Splay Tree in Data Structure
  3. B Tree in Data Structure | How to Works?
  4. Stack in Data Structure | Working | Applications
Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)
  360+ Online Courses |  1500+ Hours |  Verifiable Certificates |  Lifetime Access
4.7
Price

View Course

Related Courses

Oracle DBA Database Management System Training (2 Courses)4.9
SQL Training Program (7 Courses, 8+ Projects)4.8
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more