Question

Sort 33, 77, 22, 11, 34, 21, 88, 90, 42 using Bubble sort, show work. Write the algorithm.

Answer 1

Algorithm:
-----------
begin BubbleSort(list)
   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   return list
end BubbleSort

Sorting:
---------
Bubble sort
Original list is [33, 77, 22, 11, 34, 21, 88, 90, 42]
Iteration: 1
   > Swap 77 and 22, since they are not in correct order. Now, the list becomes [33, 22, 77, 11, 34, 21, 88, 90, 42]
   > Swap 77 and 11, since they are not in correct order. Now, the list becomes [33, 22, 11, 77, 34, 21, 88, 90, 42]
   > Swap 77 and 34, since they are not in correct order. Now, the list becomes [33, 22, 11, 34, 77, 21, 88, 90, 42]
   > Swap 77 and 21, since they are not in correct order. Now, the list becomes [33, 22, 11, 34, 21, 77, 88, 90, 42]
   > Swap 90 and 42, since they are not in correct order. Now, the list becomes [33, 22, 11, 34, 21, 77, 88, 42, 90]
   > 5 swaps happened in this iteration
   > List after iteration 1 is [33, 22, 11, 34, 21, 77, 88, 42, 90]

Iteration: 2
   > Swap 33 and 22, since they are not in correct order. Now, the list becomes [22, 33, 11, 34, 21, 77, 88, 42, 90]
   > Swap 33 and 11, since they are not in correct order. Now, the list becomes [22, 11, 33, 34, 21, 77, 88, 42, 90]
   > Swap 34 and 21, since they are not in correct order. Now, the list becomes [22, 11, 33, 21, 34, 77, 88, 42, 90]
   > Swap 88 and 42, since they are not in correct order. Now, the list becomes [22, 11, 33, 21, 34, 77, 42, 88, 90]
   > 4 swaps happened in this iteration
   > List after iteration 2 is [22, 11, 33, 21, 34, 77, 42, 88, 90]

Iteration: 3
   > Swap 22 and 11, since they are not in correct order. Now, the list becomes [11, 22, 33, 21, 34, 77, 42, 88, 90]
   > Swap 33 and 21, since they are not in correct order. Now, the list becomes [11, 22, 21, 33, 34, 77, 42, 88, 90]
   > Swap 77 and 42, since they are not in correct order. Now, the list becomes [11, 22, 21, 33, 34, 42, 77, 88, 90]
   > 3 swaps happened in this iteration
   > List after iteration 3 is [11, 22, 21, 33, 34, 42, 77, 88, 90]

Iteration: 4
   > Swap 22 and 21, since they are not in correct order. Now, the list becomes [11, 21, 22, 33, 34, 42, 77, 88, 90]
   > 1 swaps happened in this iteration
   > List after iteration 4 is [11, 21, 22, 33, 34, 42, 77, 88, 90]

Iteration: 5
   > 0 swaps happened in this iteration
   > List after iteration 5 is [11, 21, 22, 33, 34, 42, 77, 88, 90]

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