Question

Sort the following array of integer using selection and insertion sort algorithms.             Notdoing the program . Show it step by step.

            { 20   12   8   4   13   9   26   18   25   14}.

Answer 1

1)
Selection sort
Original list is [20, 12, 8, 4, 13, 9, 26, 18, 25, 14]
Iteration: 1
   > Replace element 20 with minimum number of remaining list [20, 12, 8, 4, 13, 9, 26, 18, 25, 14]
   > Minimum element found is 4. so, swap it with element at index 0 which is 20
   > List after iteration 1 is [4, 12, 8, 20, 13, 9, 26, 18, 25, 14]

Iteration: 2
   > Replace element 12 with minimum number of remaining list [12, 8, 20, 13, 9, 26, 18, 25, 14]
   > Minimum element found is 8. so, swap it with element at index 1 which is 12
   > List after iteration 2 is [4, 8, 12, 20, 13, 9, 26, 18, 25, 14]

Iteration: 3
   > Replace element 12 with minimum number of remaining list [12, 20, 13, 9, 26, 18, 25, 14]
   > Minimum element found is 9. so, swap it with element at index 2 which is 12
   > List after iteration 3 is [4, 8, 9, 20, 13, 12, 26, 18, 25, 14]

Iteration: 4
   > Replace element 20 with minimum number of remaining list [20, 13, 12, 26, 18, 25, 14]
   > Minimum element found is 12. so, swap it with element at index 3 which is 20
   > List after iteration 4 is [4, 8, 9, 12, 13, 20, 26, 18, 25, 14]

Iteration: 5
   > Replace element 13 with minimum number of remaining list [13, 20, 26, 18, 25, 14]
   > Minimum element found is 13. so, swap it with element at index 4 which is 13
   > List after iteration 5 is [4, 8, 9, 12, 13, 20, 26, 18, 25, 14]

Iteration: 6
   > Replace element 20 with minimum number of remaining list [20, 26, 18, 25, 14]
   > Minimum element found is 14. so, swap it with element at index 5 which is 20
   > List after iteration 6 is [4, 8, 9, 12, 13, 14, 26, 18, 25, 20]

Iteration: 7
   > Replace element 26 with minimum number of remaining list [26, 18, 25, 20]
   > Minimum element found is 18. so, swap it with element at index 6 which is 26
   > List after iteration 7 is [4, 8, 9, 12, 13, 14, 18, 26, 25, 20]

Iteration: 8
   > Replace element 26 with minimum number of remaining list [26, 25, 20]
   > Minimum element found is 20. so, swap it with element at index 7 which is 26
   > List after iteration 8 is [4, 8, 9, 12, 13, 14, 18, 20, 25, 26]

Iteration: 9
   > Replace element 25 with minimum number of remaining list [25, 26]
   > Minimum element found is 25. so, swap it with element at index 8 which is 25
   > List after iteration 9 is [4, 8, 9, 12, 13, 14, 18, 20, 25, 26]

Sorted list is [4, 8, 9, 12, 13, 14, 18, 20, 25, 26]

2)
Insertion sort
Original list is [20, 12, 8, 4, 13, 9, 26, 18, 25, 14]
Iteration: 1
   > place value at index 1 into sorted position
   > Insert element at index 1 which is 12 into already sorted previous array: [20]
   > List after iteration 1 is [12, 20, 8, 4, 13, 9, 26, 18, 25, 14]

Iteration: 2
   > place value at index 2 into sorted position
   > Insert element at index 2 which is 8 into already sorted previous array: [12, 20]
   > List after iteration 2 is [8, 12, 20, 4, 13, 9, 26, 18, 25, 14]

Iteration: 3
   > place value at index 3 into sorted position
   > Insert element at index 3 which is 4 into already sorted previous array: [8, 12, 20]
   > List after iteration 3 is [4, 8, 12, 20, 13, 9, 26, 18, 25, 14]

Iteration: 4
   > place value at index 4 into sorted position
   > Insert element at index 4 which is 13 into already sorted previous array: [4, 8, 12, 20]
   > List after iteration 4 is [4, 8, 12, 13, 20, 9, 26, 18, 25, 14]

Iteration: 5
   > place value at index 5 into sorted position
   > Insert element at index 5 which is 9 into already sorted previous array: [4, 8, 12, 13, 20]
   > List after iteration 5 is [4, 8, 9, 12, 13, 20, 26, 18, 25, 14]

Iteration: 6
   > place value at index 6 into sorted position
   > Insert element at index 6 which is 26 into already sorted previous array: [4, 8, 9, 12, 13, 20]
   > List after iteration 6 is [4, 8, 9, 12, 13, 20, 26, 18, 25, 14]

Iteration: 7
   > place value at index 7 into sorted position
   > Insert element at index 7 which is 18 into already sorted previous array: [4, 8, 9, 12, 13, 20, 26]
   > List after iteration 7 is [4, 8, 9, 12, 13, 18, 20, 26, 25, 14]

Iteration: 8
   > place value at index 8 into sorted position
   > Insert element at index 8 which is 25 into already sorted previous array: [4, 8, 9, 12, 13, 18, 20, 26]
   > List after iteration 8 is [4, 8, 9, 12, 13, 18, 20, 25, 26, 14]

Iteration: 9
   > place value at index 9 into sorted position
   > Insert element at index 9 which is 14 into already sorted previous array: [4, 8, 9, 12, 13, 18, 20, 25, 26]
   > List after iteration 9 is [4, 8, 9, 12, 13, 14, 18, 20, 25, 26]

Sorted list is [4, 8, 9, 12, 13, 14, 18, 20, 25, 26]