Question

Consider an array of elements arr[5]= {5,4,3,2,1} , what are the steps of  insertions done while doing insertion sort in the array.​

Answer 1

Algorithm

// Sort an arr[] of size n

insertionSort(arr, n)

Loop from i = 1 to n-1.

……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

code:-

// 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;

}

Answer 2

Answer:

Let you have array

5 4 3 2 1

You want to sort the array in the ascending order

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

2 3 4 5 1

1 2 3 4 5

These following steps are ne used.

Swap the element with its smaller at the position and repeat the process till the last index.

Explanation: