Question

Sort 33, 77, 22, 11, 34, 21, 88, 90, 42 using Selection sort and shell sort. Write the algorithms. show work. please

Answer 1

Algorithm:
-----------
begin SelectionSort(list)
   for i from 0 to length of list - 1
      minIndex = i
      for j from i+1 to length of list - 1
        if list[j] < list[minIndex]
            minIndex = j;
        end if
      end for
      swap list[i] and list[minIndex]
   end for
   return list
end SelectionSort

Selection Sort tracing:
-----------------------
Selection sort
Original list is [33, 77, 22, 11, 34, 21, 88, 90, 42]
Iteration: 1
   > Replace element 33 with minimum number of remaining list [33, 77, 22, 11, 34, 21, 88, 90, 42]
   > Minimum element found is 11. so, swap it with element at index 0 which is 33
   > List after iteration 1 is [11, 77, 22, 33, 34, 21, 88, 90, 42]

Iteration: 2
   > Replace element 77 with minimum number of remaining list [77, 22, 33, 34, 21, 88, 90, 42]
   > Minimum element found is 21. so, swap it with element at index 1 which is 77
   > List after iteration 2 is [11, 21, 22, 33, 34, 77, 88, 90, 42]

Iteration: 3
   > Replace element 22 with minimum number of remaining list [22, 33, 34, 77, 88, 90, 42]
   > Minimum element found is 22. so, swap it with element at index 2 which is 22
   > List after iteration 3 is [11, 21, 22, 33, 34, 77, 88, 90, 42]

Iteration: 4
   > Replace element 33 with minimum number of remaining list [33, 34, 77, 88, 90, 42]
   > Minimum element found is 33. so, swap it with element at index 3 which is 33
   > List after iteration 4 is [11, 21, 22, 33, 34, 77, 88, 90, 42]

Iteration: 5
   > Replace element 34 with minimum number of remaining list [34, 77, 88, 90, 42]
   > Minimum element found is 34. so, swap it with element at index 4 which is 34
   > List after iteration 5 is [11, 21, 22, 33, 34, 77, 88, 90, 42]

Iteration: 6
   > Replace element 77 with minimum number of remaining list [77, 88, 90, 42]
   > Minimum element found is 42. so, swap it with element at index 5 which is 77
   > List after iteration 6 is [11, 21, 22, 33, 34, 42, 88, 90, 77]

Iteration: 7
   > Replace element 88 with minimum number of remaining list [88, 90, 77]
   > Minimum element found is 77. so, swap it with element at index 6 which is 88
   > List after iteration 7 is [11, 21, 22, 33, 34, 42, 77, 90, 88]

Iteration: 8
   > Replace element 90 with minimum number of remaining list [90, 88]
   > Minimum element found is 88. so, swap it with element at index 7 which is 90
   > List after iteration 8 is [11, 21, 22, 33, 34, 42, 77, 88, 90]

Sorted list is [11, 21, 22, 33, 34, 42, 77, 88, 90]