Exercises 559
that describes the complexity of the procedure by counting the number of comparisons
made between pairs of elements.
INPUT: An array A containing N integers
OUTPUT: The integers sorted in nondecreasing order
for J = to 1 N - do 1
for I= IltoN -lIdo
if (A[I] > A[I + 1]) then swap their values
INPUT: An array A containing N integers
OUTPUT: The integers are sorted in nondecreasing order
RecursiveBubble (N) /* The initial call */
RecursiveBubble (k) /* The recursive procedure *!
if (k = 1) then
return
else
for I = 2 tok do
if A[I] < A[I - 1] then
swap their values
RecursiveBubble(k - 1)
- Let A be an array with N elements for some positive integer N. SelectionSort
sorts the elements of A in decreasing order by swapping the largest element in
A[1], A[21, A[31]..., A[S - 1] with A[S] where S ranges from N down to 1. Find
and solve a recurrence relation that describes the complexity of SelectionSort. Let
comparison of two elements be the key operation. Assume that the minimum opera-
tion on a set of size M requires M - 1 comparisons for any M E N.
