2. Consider the sorting algorithm shown below.

procedure sort( a₁, , an : real numbers with n 2)

for i := 1 to n-1

for j := 1 to n-1

if a_j > a_j+1 then

interchange a_j and a_j+1

endif

endfor

endfor

{a₁, , an is in increasing order}

a) Give the big-O classification of the function: __________________

b) Consider the following list, where 66 is in position 1 of the list:

66, 22, 33, 11, 55, 44

Give the contents of the list after each of the first four passes used by the algorithm.

Pass 1: __________________________________________________

Pass 2: __________________________________________________

Pass 3: __________________________________________________

Pass 4: __________________________________________________

c) Consider the following list, where 66 is in position 1 of the list:

66, 55, 44, 33, 22, 11

Give the contents of the list after each of the first four passes used by the algorithm.

Pass 1: __________________________________________________

Pass 2: __________________________________________________

Pass 3: __________________________________________________

Pass 4: __________________________________________________