C++ Program And Algorithm To Implement Insertion Sort

[795 views]


Insertion sort is a simple sorting algorithm that make the final sorted list on an array. It is not much efficient for bigger list but perfect for (quite) small data sets, much like other quadratic sorting algorithms. Insertion sort algorithm's main advantage is this algorithm is very easy and has simple implementation.

C++ Program And Algorithm To Implement Insertion Sort

Algorithm For Insertion Sort

INSERTION(A,N) This Algorithm sorts the array A with N elements. Step-1: Set A[0] := -. [Initializes sentinel element.] Step-2: Repeat Steps from 3 to 5 for K = 2,3,......,N: Step-3: Set TEMP := A[k] and PTR := K-1. Step-4: Repeat while TEMP< A[PTR]. (a) Set A[PTR=1] = A[PTR] (b) Set PTR := PTR-1. [End Of Loop] Step-5: Set A[PTR + 1] := TEMP . [End Of Step 2 Loop 2] Step-6: Return

C++ Program For Insertion Sort

// C++ program for insertion sort #include <bits/stdc++.h> using namespace std; /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } /* Driver code */ int main() { int arr[] = { 12, 11, 13, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printArray(arr, n); return 0; }

For Turbo C++ Compiler

// C++ program for insertion sort #include <iostream.h> #include <conio.h> /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } /* Main Function */ int main() { clrscr(); int arr[] = {30,21,45,67,43,20}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printArray(arr, n); getch(); return 0; }

Output

20 21 30 43 45 67
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Insertion Sort using cpp

    C++ code for Insertion Sort

    Insertion Sort simple Code in c++