Implement the algorithm kSmall, discussed in the class (Chapter 2, Section 2.4.4) by a C+ + function.

Use the first value of the array as the pivot. The partition of the array must be implemented using a function as well. Test your functions in a main program. [Hint] 1. The partition function not only rearranges the array elements but also calculates the pivots index when the partition is done. Make sure your function has correct type and parameters.

2. Please note that S1 could be empty. For example, when array has the following elements 1 3 5 2 19 3 4 If the first element is used as the pivot, S1 is empty. In this case, no swap is needed. Eventually, the array will have no change. Your partition function must take care of this special case otherwise you will have a running error like core dump. Requirements: For the function, the array parameter MUST BE passed as a pointer.

When test your functions in the main program, the array that is to be passed to the function must be generated as a dynamic array using new operator. Other requirements

Add the following information at the top of the main program: o Description of the problem to solve o Your startID and name o Due date o Instructor o Comments

For functions, add necessary documentation and comments using javadoc- style comment. Please refer to the textbook on javadoc-style comment from page 759 ~ 760 and Appendix I on page 809 (7th edition). You can also follow the document About Programming Assignments posted on D2L.

Test the algorithm by all three cases : o kth small is in S1 o kth small is the pivot o kth small in S2