Data Structures and Algorithm Analysis Selection Sort / Big-O Assignment (10 points total + 2 bonus) Due Date: Friday, February 21st, 11:59pm 1.

(5 points) Implement selection sort using the C/C++ programming language and the array data structure (use an array of type int and of size at least

15). Here is the pseudocode presented in class:

Note: You can either have the size of the array as an input and then user-input each element. Or you can hard-code the array into your source code (make sure the size is at least 15). Also, make sure you start with an unsorted array and you output (using a for loop and printf) the resulting sorted array. The for loop limits are inclusive i.e. <= instead of <.

Input: Array A[n]

for i = 0 to n-2

min = i

for j = i+1 to n-1

if( A[j] < A[min])

min = j

end if

end for

if( min != i)

swap A[i] and A[min]

end if

end for

2. (3 points) What is the worst-case time complexity of selection sort (in big-O notation)? Make sure to justify your answer (explain how you deduced it).

3. (2 points) Show that 2^3 + 7^2 + 3 + 1 = (^3 )

4. (Bonus 2 points) Show that 1 + 3 + 3^2 + 3^3 + + 3^ = (3^ )

Note: Submit your code on Blackboard, and you can submit a hard copy of your complexity analyses to me in class (you can type it or just write it by hand), or attach it with your code submission. Make sure to show all your steps.