Question

1. [C++ language] 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

I need Steps as an algorithm plus the code and screenshotes

Answer 1

The following algorithm explains insertion sort:

Algorithm
Insertion Sort
Input: Array a[0 ... n-1] with n elements which needs to be sorted.
Step 1: Read elements in array one by one from left to right, i = 0 to i = n -1
Step 2: Compare the current element(element at index i) with previous element.
Step 3: If the current element is smaller than previous element, then compare it with previous of previous element. Shift the greater elements towards right.
       Repeat Step 3. Until current element is larger than some of its predecessor.
Step 4: Insert the current element towards the right of its predecesor.

-----------------------------------------------------------------

I have included my code and screenshots in this answer. In case, there is any indentation issue due to editor, then please refer to code screenshots to avoid confusion.

------------------main.cpp-----------

#include <iostream>
using namespace std;

void print_Array(int arr[], int size)
{
   for(int i = 0; i < 10; i++)
   {
       cout << arr[i] << ", " ;
   }
   cout << endl;
}

void insertion_sort(int myArr[], int size) //insertion sorts array
{  
   int current_element;
   int prev_index;

   for (int i = 0; i < size; i++)
   {
       current_element = myArr[i];
       prev_index = i-1;
       while (prev_index >= 0 && myArr[prev_index] > current_element)
       {
           myArr[prev_index + 1] = myArr[prev_index]; //Move previous elements towards right if greater than current element
           prev_index = prev_index - 1; //Next compare previous of previous element with current element
       }
       myArr[prev_index + 1] = current_element; //when previous is smaller, insert current_element at the next position
       cout << "\nThe array after Pass "<< i << " \n";
       print_Array(myArr, size); //print array after every pass: for each i
   }
}

int main()
{
   int size = 10;
   int arr[10] = {22, 1, 7, -9, 121, 75, 89, 29, 500, 43}; //declare the array
   cout << "\n The initial array is: \n";
   print_Array(arr, size); //print initial array
  
   insertion_sort(arr, 10); //perform insertion sort

   cout << "\n The sorted array is: \n";
   print_Array(arr, size); //print sorted array
   return 0;
}

------------------Screenshot main.cpp-----------

-/pp/insertion sort/main.cpp - Sublime Text (UNREGISTERED) ti 1) 9:45 AM * main.cpp #include <iostream> using namespace std; void print_Array(int arr[], int size) { for(int i = 0; i <10; i++) { cout « arr[i] «", } cout << endl; void insertion_sort(int myArr[], int size) //insertion sorts array { int current_element; int prev_index; 16 18 19 20 for (int i = 0; i < size; i++) { current_element = myArr[i]; prev_index = i-1; whilē (prev_index >= 0 && myArr[prev_index] > current_element) myArr[prev_index + 1] = myArr[prev_index]; //Move previous elements towards right if greater than current element prev_index = prev_index - 1; /Next compare previous of previous element with current element myArr[prev_index + 1] = current_element; // when previous is smaller, insert current_element at the next position cout << "\nThe array after Pass "<< i < "\n"; print_Array(myArr, size); //print array after every pass: for each i 34 35 36 37 38 39 40 41 42 43 44 45 int main( { int size = 10; int arr[10] = {22, 1, 7, -9, 121, 75, 89, 29, 500, 43}; //declare the array cout << "\n The initial array is: \n"; print_Array(arr, size); i/print initial array insertion_sort(arr, 10); //perform insertion sort cout << "\n The sorted array is: \n"; print_Array(arr, size); //print sorted array return 0; } Line 36, Column 80; Saved -/cpp/insertion sort/main.cpp (UTF-8) Tab Size: 4 C++

------------------Output-----------

9:44 AM vs@ubuntu:-/pp/insertion sort vs@ubuntu:-/cpp/insertion sorts g++ main.cpp vs@ubuntu:-/cpp/insertion sort$ ./a.out The initial array is: 22, 1, 7, -9, 121, 75, 89, 29, 500, 43, The array after Pass O 22, 1, 7, -9, 121, 75, 89, 29, 500, 43, The array after Pass 1 i, 22, 7, 121, -9, 75, 89, 29 500, 43, The array after Pass 2 1, 7, 22, -9, 121, 75, 89, 29, 500, 43, The array after Pass 3 -9, 1, 7, 22, 121, 75, 89, 29, 500, 43, The array after Pass 4 -9, 1, 7, 22, 121, 75, 89, 29, 500, 43 The array after Pass 5 -9, 1, 7, 22, 75, 121, 89, 29, 500, 43, The array after Pass 6 -9, 1, 7, 22, 75, 89, 121, 29, 500, 43, The array after Pass 7 -9, 1, 7, 22, 29, 75, 89, 121, 500, 43, The array after Pass 8 -9, 1, 7, 22, 29, 75, 89, 121, 500, 43, The array after Pass 9 -9, 1, 7, 22, 29, 43, 75, 89, 121, 500, The sorted array is: -9, 1, 7, 22, 29, 43, 75, 89, vs@ubuntu:-/pp/insertion sorts | 121, 500,

-------------------------------------

I hope this helps you,

Please rate this answer if it helped you,

Thanks for the opportunity