Question: (a) Show the steps involved in the application of a bubble sort to the list c, a, e, b, d, where these letters have their natural alphabetical order.

(b) Apply the same sequence of interchanges as required in part (a) to the list 1, 2, 3, 4, 5; that is, if it is necessary to interchange the second and third elements at a certain stage in the bubble sort of (a), then interchange the second and third elements at the same stage in the "sort" of 1, 2, 3, 4, 5. The final sequence is 2, 4, 1, 5, 3, which describes the order in which the elements of c, a, e, b, d must be taken to list them in order.

(c) Describe an algorithm whose input is a list a₁, a₂, ., an whose natural order is a_i1 . a_i2 . . , a_in and whose output is the sequence of indices i₁, i₂, ., i_n (in this order).