Analysis of Algorithms

Question 1) a) Write an algorithm for sorting a list of integer numbers using the bubble sort algorithm write what you understood from the algorithm using your own ENGLISH DESCRIPTION. No point for a code here).

Ensure you provide enough detail and follow the definition of an algorithm as we studied in video lectures.

b) Assume you are given the numbers 4, 2, 3, 1. Show step by step how your described algorithm in part (a) works on the given list of numbers and moves them through the list until the algorithm terminates and the list is sorted in increasing order.

c) Now analyze the time complexity of the bubble sort algorithm STEP BY STEP as what we did for the linear search. Show all your work. Then specify the worst-case time complexity of bubble sort in Big-O notation.