C++ Program And Algorithm To Implement Insertion Sort

[10143 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; }