Question

data structure

Basic Sorts Each of the following sorting algorithms is applied to the following array of numbers: 5 6 1 8 2 4 37 The array at each iteration is shown for each algorithm. However, for each algorithm execution description, there is one error. Highlight the error and then describe why it is wrong at that point Bubble (not optimized): 5 6 18 2437 51 6 2 4 3 78 15 2 4 3 6 7 8 1 2 4 3 5 6 7 8 12 4 3 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Selection 5 6 18 24 37 1658 2 437 1 2 5 8 6 4 3 7 1 2 3 8 6 4 5 7 1 2 3 4 6 8 5 7 1 2 3 4 5 8 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Insertion 5 6 18 2 4 3 7 5 6 18 24 3 7 1 5 6 8 2 4 3 7 15 68 2 4 3 7 1 25 68 4 3 7 1 2 3 5 6 8 4 7 1 2 3 4 5 6 8 7 1 2 3 4 5 6 7 8

Answer 1

Bubble (not optimized):

original array-> 5 6 1 8 2 4 3 7

1st iteration-> 5 1 6 2 4 3 7 8
2nd iteration-> 1 5 2 4 3 6 7 8
3rd iteration-> 1 2 4 3 5 6 7 8
4th iteration-> 1 2 4 3 5 6 7 8
5th iteration-> 1 2 3 4 5 6 7 8
6th iteration-> 1 2 3 4 5 6 7 8
7th iteration-> 1 2 3 4 5 6 7 8

There is error in 4th iteration-> 1 2 4 3 5 6 7 8

Step by step execution of 4th iteration:

Array after 3rd iteration is 1 2 4 3 5 6 7 8

highlighted elements are compared and if the first element is greater than second element then they are swapped with each other.

1 2 4 3 5 6 7 8

1 2 4 3 5 6 7 8

1 2 4 3 5 6 7 8 <------------- 4,3 will get swapped because 3<4

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

The correct order of elements will be-> 1 2 3 4 5 6 7 8

Selection:

original array-> 5 6 1 8 2 4 3 7

1st iteration-> 1 6 5 8 2 4 3 7
2nd iteration-> 1 2 5 8 6 4 3 7
3rd iteration-> 1 2 3 8 6 4 5 7
4th iteration-> 1 2 3 4 6 8 5 7
5th iteration-> 1 2 3 4 5 8 6 7
6th iteration-> 1 2 3 4 5 6 7 8
7th iteration->  1 2 3 4 5 6 7 8

There is error in 6th iteration-> 1 2 3 4 5 6 7 8

Array after 5th iteration is 1 2 3 4 5 8 6 7

1 2 3 4 5 8 6 7 <--------------- highlighted part is unsorted part

minimum value element in the unsorted part is 6, therefore 8,6 will get swapped then the new sequence will become

1 2 3 4 5 6 8 7

The correct order of elements will be-> 1 2 3 4 5 6 8 7

Insertion:

original array-> 5 6 1 8 2 4 3 7

1st iteration-> 5 6 1 8 2 4 3 7
2nd iteration-> 1 5 6 8 2 4 3 7
3rd iteration-> 1 5 6 8 2 4 3 7
4th iteration-> 1 2 5 6 8 4 3 7
5th iteration-> 1 2 3 5 6 8 4 7
6th iteration-> 1 2 3 4 5 6 8 7
7th iteration->  1 2 3 4 5 6 7 8

There is error in 5th iteration-> 1 2 3 5 6 8 4 7

Array after 4th iteration is 1 2 5 6 8 4 3 7 <--- highlighted part is the sorted part

In the 5th iteration 4 should be insert in the sorted part then the new sequence will become 1 2 4 5 6 8 3 7

The correct order of elements will be-> 1 2 4 5 6 8 3 7