1. (35 pts) Use figures 1-3 in the attached illustrations as models to show the operations of selection, insertion and shell sorts on the input array {1, 6, 7,5, 0, 9, 8, 4, 3, 2}. For shell sort, use the gap values 7, 3, and 1, in that order. illustration of operations: Comparison Sorts Legend: - - Solid lines indicate elements compared. Double arrows indicate elements moved. Fig 1: Operation of selection sort on |0|9 | 8 |1 | 2 | 3 | 7 |6|4| 5 0[1 | 2 | 3 | 4 | 5 | 7 | 6 | 8 | 9 | 0 | 1 | 2 | 9 | 6 | 5 |7161415 0 | 1 | 2 | 3 | 8 | 9|716415) 01 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 15 16 17 18 19 Fig 2: Operation of insertion sort on with gap values 5, 3 and 1. Pass 1, gap = 5 03 03 97 25 Array after pass 1: |0|716 | 1 | 2 | 3 |9 | 3 | 4 | 5 Pass 2, gap = 3 0 1 7 5 9261 Array after pass 2: | 2 | 3 | 116 | 5 | 5 | 9 | 8 || Pass 3, gap = 1 0|2|3 | 116 55198 11 10 | 1|2|3 | 5 | 5 | 6 | 7 | 8 | 9 Array after pass 3