- C++ Programming Examples
- C++ Programming Examples
- C++: Hello World
- C++: Get Input
- C++: Print Integer
- C++: Add two numbers
- C++: Add, Sub, Multiply, Div
- C++: Add Digits
- C++: Find Average and Percentage
- C++: Find Arithmetic Mean
- C++: Sum of n Natural Numbers
- C++: Sum of n Numbers
- C++: Square's Area and Perimeter
- C++: Rectangle's Area and Perimeter
- C++: Triangle's Area and Perimeter
- C++: Area and Circumference
- C++: Find Simple Interest
- C++: Fahrenheit to Celsius
- C++: Celsius to Fahrenheit
- C++: Print Prime Numbers
- C++: Reverse a Number
- C++: Swap Two Numbers
- C++: Print Multiplication Table
- C++: Find Factorial of a Number
- C++: Find Factors of a Number
- C++: Find HCF and LCM
- C++: Create a Calculator
- C++: Count Digits in a Number
- C++: First and Last Digit Sum
- C++: Product of Number Digits
- C++: Sum of Squares of Digits
- C++: Interchange Digits of Number
- C++ if-else Programs
- C++: Check Even or Odd
- C++: Check Prime or Not
- C++: Check Alphabet or Not
- C++: Check Vowel or Not
- C++: Check Leap Year or Not
- C++: Check Reverse equals Original
- C++: Check Perfect Number
- C++: Check Palindrome or Not
- C++: Check Armstrong or Not
- C++: Divisibility Test
- C++: Find Labor Wage
- C++: Find Discounted Price
- C++: Find Shipping Charge
- C++: Find Telephone Bills
- C++: Calculate Student Grade
- C++: Largest of Two Numbers
- C++: Largest of Three Numbers
- C++ Number Conversion
- C++: Decimal to Binary
- C++: Decimal to Octal
- C++: Decimal to Hexadecimal
- C++: Binary to Decimal
- C++: Binary to Octal
- C++: Binary to Hexadecimal
- C++: Octal to Decimal
- C++: Octal to Binary
- C++: Octal to Hexadecimal
- C++: Hexadecimal to Decimal
- C++: Hexadecimal to Binary
- C++: Hexadecimal to Octal
- C++ Pattern Programs
- C++: Pattern Programs
- C++: Print Diamond Pattern
- C++: Print Floyd's Triangle
- C++: Print Pascal's Triangle
- C++ Array Programs
- C++: 1D Array Program
- C++: Linear Search
- C++: Binary Search
- C++: Largest Element in an Array
- C++: Smallest Element in an Array
- C++: Find Second Largest Element
- C++: Find Second Smallest Element
- C++: Sum of All Elements
- C++: Multiply All Elements
- C++: Element in Even Position
- C++: Element in Odd Position
- C++: Print Even Numbers in Array
- C++: Print Odd Numbers in Array
- C++: Count Even or Odd Numbers
- C++: Sum of Even or Odd Numbers
- C++: Count Positive, Negative, Zero
- C++: Reverse an Array
- C++: Insert an Element
- C++: Delete an Element
- C++: Merge two Arrays
- C++: Bubble Sort
- C++: Selection Sort
- C++: Insertion Sort
- C++: Common Elements
- C++: 2D Array Programs
- C++: Add Two Matrices
- C++: Subtract Two Matrices
- C++: Transpose Matrix
- C++: Multiply Two Matrices
- C++: 3D Array Programs
- C++ String Programs
- C++: Print String
- C++: Find String Length
- C++: Compare Two Strings
- C++: Copy String
- C++: String Concatenation
- C++: Reverse a String
- C++: Delete Vowels from a String
- C++: Delete a Word from a String
- C++: Count Characters in a String
- C++: Count Words in a String
- C++: Frequency of Words
- C++: Remove Spaces from Strings
- C++: Sort a String
- C++: Uppercase to Lowercase
- C++: Lowercase to Uppercase
- C++: Swap Two Strings
- C++: Check the Anagram or Not
- C++: Capitalize All Words in a String
- C++: Get Numbers from a String
- C++ File Programs
- C++: Read a File
- C++: Write Content to a File
- C++: Append Data to a File
- C++: Read and Display File
- C++: Copy a File
- C++: Merge Two Files
- Count Characters in a File
- C++: Capitalize Every Word
- C++: List Files in Directory
- C++: Delete a File
- C++: Encrypt and Decrypt a File
- C++ Misc Programs
- C++: Print ASCII Value
- C++: Add Binary Numbers
- C++: Generate Random Numbers
- C++: Print a Smiling Face
- C++: Days into Years and Months
- C++: Add Two Numbers using Pointer
- C++: Print Fibonacci Series
- C++: Generate Armstrong Numbers
- C++: Find nCr and nPr
- C++: Get IP Address
- C++: Print Date and Time
- C++: Shutdown and Restart Computer
- C++ Programming Tutorial
- C++ Tutorial
C++ Program for Insertion Sort
In this article, you will learn and get code to sort an array using the insertion sort technique in C++. The following programs are listed in insertion order:
Before going through these programs, if you're not aware of the steps and logic used behind insertion sort, then refer to the insertion sort algorithm and example to get all the things you need.
Insertion Sort in C++
To sort an array using the insertion sort technique in C++ programming, you have to ask the user to enter the size of the array and then enter elements of that size in random order. After receiving the inputs, sort the given array in ascending order using insertion sort as shown in the program given below:
The question is, "Write a program in C++ to implement insertion sort." Here is the answer:
#include<iostream> using namespace std; int main() { int arr[50], tot, i, j, k, elem, index; cout<<"Enter the Size for Array: "; cin>>tot; cout<<"Enter "<<tot<<" Array Elements: "; for(i=0; i<tot; i++) cin>>arr[i]; for(i=1; i<tot; i++) { elem = arr[i]; if(elem<arr[i-1]) { for(j=0; j<=i; j++) { if(elem<arr[j]) { index = j; for(k=i; k>j; k--) arr[k] = arr[k-1]; break; } } } else continue; arr[index] = elem; } cout<<"\nThe New Array (Sorted Array):\n"; for(i=0; i<tot; i++) cout<<arr[i]<<" "; cout<<endl; return 0; }
This program was built and runs under the Code::Blocks IDE. Here is its sample run:
Now supply the size, say 10, for the array, and press ENTER. Here is the output you will see:
Now supply any 10 numbers as 10 array elements, say 10, 1, 9, 2, 8, 3, 7, 4, 6, and 5, one by one. After supplying all 10 inputs, press the ENTER key to sort and print the new array as shown in the output given below:
The following is how the above program's dry run (receiving user input) goes:
- When the user enters the size, say 10, for the array, it gets stored in tot. So tot=10
- Now we've created a for loop to receive 10 inputs as 10 elements.
- That is, until the condition i<tot (of the for loop) evaluates to false, the statement inside the loop continues to execute.
- And each time we enter the loop, we get a number in the arr.
- At the first run of the for loop, its initialization (first) part executes at first, but only once. As a result, i=0 at first.
- And the condition i<tot gets evaluated. That is, the condition i<tot or 0<10 evaluates to be true, so the program flow goes inside the loop and receives a number from the user. The number gets stored in arr[i] or arr[0].
- The value of i is now increased. So i=1. And the condition i<tot is evaluated once more with a new value of i.
- Also, the condition i<tot or 1<10 evaluates to true the second time, so another value is received and initialized to arr[1]. In this way, 10 elements gets initialized to arr[] in such a way that the first element gets stored in arr[0], the second in arr[1], and so on, up to the tenth element in arr[9].
And the dry run of insertion sort code in the above program with user input, 10 as size, and 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 as elements of the array, goes like this:
- The for loop starts with 1. As a result, i = 1 at first.
- The condition i<tot or 1<10 evaluates to be true, therefore program flow goes inside the loop, and arr[i] or arr[1] or 1 gets initialized to elem
- Now the condition (of if), elem<arr[i-1] or 1<arr[1-1] or 1<arr[0] or 1<10 evaluates to be true, therefore program flow goes inside if's body.
- There is another for loop; initially j=0 and the condition j<=i or 0<=1 evaluates to be true, therefore program flow goes inside the loop.
- And the condition (of if), elem<arr[j] or 1<arr[0] or 1<10 evaluates to true, program flow enters the if's body, and j or 0 is initialized to index.
- There is one more for loop; with this loop, the value of i (1) gets initialized to k. So k=1, and the condition k>j or 1>=0 evaluates to be true, therefore program flow goes inside the loop, and arr[k-1] or arr[1-1] or arr[0] or 10 gets initialized to arr[k] or arr[1].
- Now the value of k gets decremented. So k=0
- The condition, k>j or 0>0 evaluates to be false; therefore, execution of this loop gets ended for now. The execution of the outer for loop is skipped when the break keyword is used.
- Now the value of elem (1) gets initialized to arr[index] or arr[0]. So arr[0]=1
- Finally, the two elements, that is, element at the first and second positions, get exchanged. As a result, arr[0] = 1 and arr[1] = 10.
- This process continues, until the condition of the for (the outermost) evaluates to be false.
- Now print the value of arr[], which will be the same array in sorted form.
Print the array after each sort
After each insertion sort sort, a new array is printed in this program. After watching the output of this program, you can understand its in-depth detail in sorting the elements.
#include<iostream> using namespace std; int main() { int arr[50], tot, i, j, k, elem, index; cout<<"Enter the Size for Array: "; cin>>tot; cout<<"Enter "<<tot<<" Array Elements: "; for(i=0; i<tot; i++) cin>>arr[i]; for(i=1; i<tot; i++) { elem = arr[i]; if(elem<arr[i-1]) { for(j=0; j<=i; j++) { if(elem<arr[j]) { index = j; for(k=i; k>j; k--) arr[k] = arr[k-1]; break; } } } else continue; arr[index] = elem; cout<<"\nStep "<<i<<": "; for(j=0; j<tot; j++) cout<<arr[j]<<" "; } cout<<"\n\nThe New Array (Sorted Array):\n"; for(i=0; i<tot; i++) cout<<arr[i]<<" "; cout<<endl; return 0; }
Here is its sample run with the same user input as provided in the previous program's sample run:
Insertion Sorting with a Function
This is the last program in this article that does the same job as the very first program in this article. The only difference is that this program uses a user-defined function, insertionSort(), to sort an array entered by the user.
This function receives an array and its size as its two arguments.
#include<iostream> using namespace std; void insertionSort(int [], int); int main() { int arr[50], tot, i; cout<<"Enter the Size for Array: "; cin>>tot; cout<<"Enter "<<tot<<" Array Elements: "; for(i=0; i<tot; i++) cin>>arr[i]; insertionSort(arr, tot); cout<<"\nThe New Array (Sorted Array):\n"; for(i=0; i<tot; i++) cout<<arr[i]<<" "; cout<<endl; return 0; } void insertionSort(int arr[], int tot) { int i, elem, j; for(i=1; i<tot; i++) { elem = arr[i]; j = i-1; while((elem<arr[j]) && (j>=0)) { arr[j+1] = arr[j]; j--; } arr[j+1] = elem; } }
Here is its sample run with user input, 10 as size, and 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 as elements for the array:
The same program in different languages
« Previous Program Next Program »