Question 1. Please be detailed. Will Rate Insertion Sort: An Example (CLRS) 4 6

Question

Question 1. Please be detailed. Will Rate

Insertion Sort: An Example (CLRS) 4 6 1 3 6 13 (c) 2 4 1 2 3 4 5 6 e) 1 (D 1 2 3 4 56 Figure 2.2 The operation of INSERTION-SORT on the array A = (5, 2, 4, 6, 1.3). Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles. (a)-(e) The iterations of the for loop of lines 1-8. In each iteration. the black rectangle holds the key taken from Aljl. which is compared with the values in shaded rectangles to its left in the test of line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows indicate where the key is moved to in line 8. () The final sorted array ms (40+10 extra pts) show the working of insertion sort on the array it, 0 pts) Use the figure (CLRS, Fig 2.2) on page 15 of the lecture slides for Chapter 7 as a model and 3, 5, 6, 4, 2,7, 9, 8, 0]. You need to insertion sort algorithm given in lecture. (10 pts) Use the figure (CLRS, Fig 2.3) on page 15 of the lecture slides for Chapter 7 as a model and show the working of indicate which elements of the array are compared and/or moved after each iteration of the main loop in the p=1. g:4, r-8. You need to show the content of nd 8 i e

Explanation / Answer

nsertion sort : Insertion is good for small elements only because it requires more time for sorting large number of elements. In insertion sort sort array by checking one element to other if next element is bigger then previous just swap them this is the main logic of insertion sort. In following program you can understand better.

public class InsertionSorting {

  public static void main(String a[]){

        int[] unsortedArray = {19,45,34,22,67,47,77};

insertionSort(unsortedArray);

    }

public static void insertionSort(int[] values) {

int temp;

for(int i=0;i<values.length;i++) { //Outer loop

for(int j=i;j>0;j--) { //inner loop

if(values[j]<values[j-1]) {

temp=values[j];

values[j]=values[j-1];

values[j-1]=temp;

}

}

}

System.out.println("insertion sort : "+Arrays.toString(values));

}

}

Explanation :

        int[] arr = {19,45,34,22,67,47,77};

pos= 0, 1, 2, 3, 4, 5, 6

when i=0

start loop arr[i] value is 19

j=0 but j>0 not true so again inner loop will not run go to outer loop i++

when i=1

j=1 and also j>0 true

check arr[j] <arr[j-1] mean arr[1] < arr[0] means 45<19 false

j-- check j>0 not true so again inner loop will not run go to outer loop i++

when i=2

j=i mean j=2 and also j>0 true

check arr[j] > arr[j-1] mean arr[2] < arr[1] means 34<45 true

swap value now arr will be

{19,34,45,22,67,47,77};

j-- then j=1;

check arr[j] > arr[j-1] mean arr[1] < arr[0] means 34<19 false

j-- j=0 j>0 false again outer loop will run i++

Now for i reach 3

Same above thing will repeat till i=5 because condition is i<arr.length

then arr will be {19, 22 ,34 , 45 ,47 ,67 ,77};

If you have any query please comment :)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.