(N) Sorting a string¶

Goal: I will practice implementing recursion.

Instructions: Retrieve the code template: templates/02/string_sort/ -> student/02/string_sort/. For automated testing, the template contains the definitions RECURSIVE_FUNC_IOS and RECURSIVE_FUNC_SORT You need not care about them, and you must not change them.

In the code template, implement two functions: index_of_smallest and sort. The first-mentioned one returns the index, which stores the smallest character of the string. Here, smallest character is the one, the ASCII code of which is the smallest. This order is the default one, which is used by the operators: <, >, <= and >=. The other function sorts the characters of the string based on their ASCII codes by calling the first-mentioned function.

Since the aim is to write a recursive functions, loops (for or while) are not allowed.

If you want, you can implement an utility function swap(string& s, unsigned int ind1, unsigned int ind2), which works in the same way as the swap function implemented in an earlier exercise, but now the function receives a string, the characters of which will be swapped, as well as two indices, from where the characters to be swapped can be found. (This function is not recursive, and it needs no iteration either.)

Example executions:

Enter a string: 3746
Index of smallest character: 0
Sorted string: 3467

Enter a string: palindrome
Index of smallest character: 1
Sorted string: adeilmnopr

Tips for completing the assignment:

• Start by thinking how to find a trivial case and write it as code.

• After that try to divide the problem into a smaller instance of the same problem.

• You can assume that the smallest character occurs in the string only once.

• Since index_of_smallest finds the index where the smallest character can be found, there is most probably no need to call substr function. Namely, calling it would change the original indices. Instead, you will most probably need two index parameters: one for telling the current index, and the other telling the index of the smallest character from those indices processed so far.

• By implementing only the function index_of_smallest, you can earn part of the points. However, the function sort does not need very many code lines assuming that you have implemented the swap function. (Even three executable lines is enough.)