Simple Insertion Sort Program in C++
Definition
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages like simple implementation, efficient for (quite) small data sets, more efficient in practice than most other simple quadratic algorithms, adaptive, stable, in-place; i.e., only requires a constant amount of additional memory space, online; i.e., can sort a list as it receives it.
Example Program
/* Simple Insertion Sort Program in C++*/
/* Data Structure C++ Programs,C++ Array Examples */
#include <iostream>
#include<conio.h>
#include<stdlib.h>
#define MAX_SIZE 5
using namespace std;
void insertion(int[]);
int main() {
int arr_sort[MAX_SIZE], i, j, a, t;
cout << "Simple C++ Insertion Sort Example - Array\n";
cout << "\nEnter " << MAX_SIZE << " Elements for Sorting : " << endl;
for (i = 0; i < MAX_SIZE; i++)
cin >> arr_sort[i];
cout << "\nYour Data :";
for (i = 0; i < MAX_SIZE; i++) {
cout << "\t" << arr_sort[i];
}
for (i = 1; i < MAX_SIZE; i++) {
t = arr_sort[i];
j = i - 1;
while (j >= 0 && arr_sort[j] > t) {
arr_sort[j + 1] = arr_sort[j];
j = j - 1;
}
arr_sort[j + 1] = t;
cout << "\nIteration : " << i;
for (a = 0; a < MAX_SIZE; a++) {
cout << "\t" << arr_sort[a];
}
}
cout << "\n\nSorted Data :";
for (i = 0; i < MAX_SIZE; i++) {
cout << "\t" << arr_sort[i];
}
getch();
}
Sample Output
Simple Insertion Sort Example - Array
Enter 5 Elements for Sorting
3244
23
12
34
1
Your Data : 3244 23 12 34 1
Iteration 1 : 23 3244 12 34 1
Iteration 2 : 12 23 3244 34 1
Iteration 3 : 12 23 34 3244 1
Iteration 4 : 1 12 23 34 3244
Sorted Data : 1 12 23 34 3244
------------------
(program exited with code: 0)
Press any key to continue . . .
Sorting Programs
- Simple Bubble Sort Program in C++
- Simple Bubble Sort Program using functions in C++
- Simple Insertion Sort Program in C++
- Simple Insertion Sort Program using functions in C++
- Simple Selection Sort Program in C++
- Simple Selection Sort Program using functions in C++
- Simple Quick Sort Program in C++
- Simple Merge Sort Program in C++
- Simple Shell Sort Program in C++
- Simple Shell Sort Program using functions in C++
- Simple Heap Sort Program in C++
Read More Articles
- Simple Merge Sort Program in C++
- Scope Resolution Operator In C++
- Simple Program for Virtual Functions Using C++ Programming
- Simple Class Example Program For Find Prime Number In C++
- Simple Example Program For Parameterized Constructor In C++
- Define Constructor in Outside Class Example Program In C++
- Simple Example Program For Copy Constructor In C++
- Simple Program for Function Overloading Using C++ Programming
- Simple Program for Single Inheritance Using C++ Programming
- Simple Program for Inline Function without Class Using C++ Programming
- Simple Example Program For Constructor Overloading In C++
- Factorial Using Function Example Program In C++
- Simple Example Program for Inline Function Using C++ Programming
- Simple Addition ( Add Two Integers ) Example Program
- Simple Example Program For Constructor In C++
- Simple Program for Read user Input Using cin
- Simple Stack Program in C++ Programming
- Factorial Using Loop Example Program In C++
- Simple Program for Friend Function Using C++ Programming
- Simple Program for Static Data and Member Function Using C++ Programming
- Simple Program for Multiple Inheritance Using C++ Programming
- Simple Program for Unary Operator Overloading Using C++ Programming
- Simple Copy Constructor Example Program For Find Factorial In C++
- Do While Loop Example Program In C++
- Simple Program for Virtual Base Class Using C++ Programming