C++ Program And Algorithm To Implement Insertion Sort

(195 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

Solution Worked 1 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote

        


Comments



Search


Earn Money by Submitting Articles
Start submutting articles. Click here to get started
Play 2048 Game Online

Play Duckhunt Online
Search Tags

    Insertion Sort using cpp

    C++ code for Insertion Sort

    Insertion Sort simple Code in c++