Question

1. Show full work: Please make sure to start the comparison with -infinity and NO NOT COUNT SWAPS!
2. Sort the list A[ ]={ 20, 13,4, 34, 5, 15, 90, 100, 75, 102, 112, 1} using Insertion Sort and determine the total number of comparisons made (do not count swaps)

Answer 1

Answer:

Step 1:

Given array:

20	13	4	34	5	15	90	100	75	102	112	1
0	1	2	3	4	5	6	7	8	9	10	11

Step 2:

Leftmost are always sorted. We begin with the record in position 0 in the sorted portion, and we will be moving the record in position 1 to the left until it is sorted.

Processing record in position 1. Move the processing record to the left until it reaches the correct position.

Compare 20 and 13, as 13<20 so swap the values.

13

20

4

34

5

15

90

100

75

102

112

1

Step 3:

Processing record in position 2. Move the processing record to the left until it reaches the correct position.

4<20 swap the values.

13

4

20

34

5

15

90

100

75

102

112

1

4<13 swap the values.

4

13

20

34

5

15

90

100

75

102

112

1

Step 4:

Processing record in position 3. Move the processing record to the left until it reaches the correct position. 34 is at their correct place as 34>20.

Step 5:

Processing record in position 4. Move the processing record to the left until it reaches the correct position.

5<34, swap the values.

4

13

20

5

34

15

90

100

75

102

112

1

5<20, swap the values.

4

13

5

20

34

15

90

100

75

102

112

1

5<13, swap the values.

4

5

13

20

34

15

90

100

75

102

112

1

Step 6:

Processing record in position 5. Move the processing record to the left until it reaches the correct position.

15<34, swap the values.

4

5

13

20

15

34

90

100

75

102

112

1

15<20, swap the values.

4

5

13

15

20

34

90

100

75

102

112

1

Step 7:

Processing record in position 6. Move the processing record to the left until it reaches the correct position. 90 is at correct position as 90>34.

Step 8:

Processing record in position 7. Move the processing record to the left until it reaches the correct position. 100 is at correct position as 100>90.

Step 9:

Processing record in position 8. Move the processing record to the left until it reaches the correct position.

75<100, swap the values.

4

5

13

15

20

34

90

75

100

102

112

1

75<90, swap the values.

4

5

13

15

20

34

75

90

100

102

112

1

Step 10:

Processing record in position 9. Move the processing record to the left until it reaches the correct position. 102 is at correct position as 102>100.

Step 11:

Processing record in position 10. Move the processing record to the left until it reaches the correct position. 112 is at correct position as 112>102.

Step 12:

Processing record in position 11. Move the processing record to the left until it reaches the correct position.

1<112, swap the values.

4

5

13

15

20

34

75

90

100

102

1

112

1<102, swap the values.

4

5

13

15

20

34

75

90

​​​​​​​100

1

102

112

1<100, swap the values.

4

5

13

15

20

34

75

90

​​​​​​​1

100

102

112

1<90, swap the values.

4

5

13

15

20

34

75

1

90

100

102

112

1<75, swap the values.

4

5

13

15

20

34

1

75

​​​​​​​90

100

102

112

1<34, swap the values.

4

5

13

15

20

1

34

75

​​​​​​​90

100

102

112

1<20, swap the values.

4

5

13

15

1

20

​​​​​​​34

75

​​​​​​​90

100

102

112

1<15, swap the values.

4

5

13

1

15

​​​​​​​20

​​​​​​​34

75

​​​​​​​90

100

102

112

1<13, swap the values.

4

5

1

13

15

​​​​​​​20

​​​​​​​34

75

​​​​​​​90

100

102

112

1<5, swap the values.

4

1

5

13

15

​​​​​​​20

​​​​​​​34

75

​​​​​​​90

100

102

112

1<4, swap the values.

1

4

5

13

15

​​​​​​​20

​​​​​​​34

75

​​​​​​​90

100

102

112

Step 13:

Finally list is sorted.

Total comparisons made: 26

Please give thumbsup, or do comment in case of any query. Thanks.