Suppose the elements in the array are A = < 2, 13, 5, 18, 14, 20 >. Can this array be represented in INSERTION SORTING? Justify your answer with all the steps.

Q.) Suppose the elements in the array are A = < 2, 13, 5, 18, 14, 20 >. Can this array be represented in INSERTION SORTING? Justify your answer with all the steps.

 Subject: Data Structures - II

Yes, the given array can be represented in Insertion Sort. Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Here are the steps to sort the given array A = < 2, 13, 5, 18, 14, 20 > using Insertion Sort:

  1. Step 1: The first element in the array is already sorted. So, start from the second element (13), compare it with the first element and swap them if necessary.

    Array after Step 1: < 2, 13, 5, 18, 14, 20 >

  2. Step 2: Move to the next element (5). Compare it with the elements before it. Since 5 is less than 13, move 13 one position to the right and place 5 in its place.

    Array after Step 2: < 2, 5, 13, 18, 14, 20 >

  3. Step 3: Move to the next element (18). Since 18 is greater than all the elements before it, leave it in its place.

    Array after Step 3: < 2, 5, 13, 18, 14, 20 >

  4. Step 4: Move to the next element (14). Compare it with the elements before it. Since 14 is less than 18 but greater than 13, move 18 one position to the right and place 14 in its place.

    Array after Step 4: < 2, 5, 13, 14, 18, 20 >

  5. Step 5: Move to the last element (20). Since 20 is greater than all the elements before it, leave it in its place.

    Array after Step 5: < 2, 5, 13, 14, 18, 20 >

So, the array A = < 2, 13, 5, 18, 14, 20 > can be sorted using Insertion Sort.

Here is a table that shows the array after each step:

Step Array
1 < 2, 13, 5, 18, 14, 20 >
2 < 2, 5, 13, 18, 14, 20 >
3 < 2, 5, 13, 18, 14, 20 >
4 < 2, 5, 13, 14, 18, 20 >
5 < 2, 5, 13, 14, 18, 20 >

In each step, the elements to the left of the current element are sorted, and the elements to the right are yet to be sorted. The current element is inserted in the correct position among the sorted elements. This process continues until all the elements are sorted.