Question

1. (C++) Write down the steps how insertion sort for sorting the following elements in an array:

22, 1, 7, -9, 121, 75, 89, 29, 500, 43

Answer 1

Insertion sort:

• First it will assume array into two parts i.e sorted part and unsorted part.
• Selecting the elements sequentially in array.
• Selecting element in unsorted part and inserting in sorted part where this element is more than predecessor and less than the successor.

Given array: 22 1 7 -9 121 75 89 29 500 43

Step 1:  22 1 7 -9 121 75 89 29 500 43

• First element 22 is the sorted part.

Step 2:  1 22 7 -9 121 75 89 29 500 43

• 1 is inserting before the 22. Becuase 1 is less than 22.

Step 3: 1 7 22 -9 121 75 89 29 500 43

• 7 is inserting between 1 and 22 because 7 is more than 1 and less than 22.

Step4: -9 1 7 22 121 75 89 29 500 43

• -9 is lowest element on sorted part. So -9 is inserting in first.

Step5: -9 1 7 22 121 75 89 29 500 43

• 121 is more than 22. So inserting 121 at after the 22 of sorted part.

Step 6: -9 1 7 22 75 121 89 29 500 43

• inserting 75 between 22 and 121 because 75 is more than 22 and less than 121.

Step 7: -9 1 7 22 75 89 121 29 500 43

• inserting 89 between 75 and 121 because 89 is more than 75 and less than 121.

Step 8: -9 1 7 22 29 75 89 121 500 43

• inserting 29 between 22 and 75 because 29 is more than 22 and less than 75.

Step 9: -9 1 7 22 29 75 89 121 500 43

• inserting 500 after the 121 because it is the maximum element in all sorted elements.

Step 10: -9 1 7 22 29 43 75 89 121 500

• Inserting 43 between 29 and 75 becasue 43 is more than 29 and less than 75.

After these steps array is in sorted order.

Program:

#include<bits/stdc++.h>
using namespace std;
//function to print an array
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
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;

//printing each step of insertion sort.
cout << "Step " << i+1 << ": ";
printArray(arr, n); //calling the function to print the array.
}
}

int main()
{
int arr[] = {22, 1, 7, -9, 121, 75, 89, 29, 500, 43}; //array initialization.
int n = sizeof(arr) / sizeof(arr[0]); //calculating the size of the array.

//printing the array of step 1.
cout << "Step 1: ";
printArray(arr, n);

insertionSort(arr, n); //calling the function to sort the remaining array.
return 0;
}

1 2 3 5 6 #include<bits/stdc++.h> using namespace std; //function to print an array void printArray (int arr[], int n) { int i; for (i = 0; i <n; i++) cout << arr[i] << " "; cout << endl; 7 } void insertionSort (int arr[], int n) int i, key, j; for (i = 1; i <n; i++) { 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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 (>= 0 && arrijl > key) { arrij + 1] = arr[j]; j =) - 1; } arr(j + 1] = key; 25 26 27 28 29 30 //printing each step of insertion sort. cout << "Step " « i+1 << ": "; printArray (arr, n); // calling the function to print the array. ههه

int main() int arr[] = {22, 1, 7, -9, 121, 75, 89, 29, 500, 43); //array initialization. int n = sizeof (arr) / sizeof (arr[0]); //calculating the size of the array. 31 32 33 34 35 36 37 38 39 40 41 42 43 44 //printing the array of step 1. cout << "Step 1: "; printArray(arr, n); insertionSort (arr, n); //calling the function to sort the remaining array. return 0;

output:

Step 1: 22 1 7 -9 121 75 89 29 500 43 Step 2: 1 22 7 -9 121 75 89 29 500 43 Step 3: 17 22 -9 121 75 89 29 500 43 Step 4: -9 17 22 121 75 89 29 500 43 Step 5: -9 17 22 121 75 89 29 500 43 Step 6: -9 17 22 75 121 89 29 500 43 Step 7: -91 7 22 75 89 121 29 500 43 Step 8: -9 17 22 29 75 89 121 500 43 Step 9: -9 17 22 29 75 89 121 500 43 Step 10: -9 1 7 22 29 43 75 89 121 500 execution time : 0.060 s Process returned o (Oxo) Press any key to continue.

Note: my friend if you have any questions or queries comment below. i am happy to answer your all questions. I will sort out your queries. Thank you my friend.