Jan-14-2021, 07:49 AM
(This post was last modified: Jan-14-2021, 07:49 AM by deanhystad.)
I do not understand your request. You talk about having 2 recursive functions, but you have no recursive functions. Recursion is when a function calls itself. Neither of your functions do that.
I don't know why you want a recursive sort. Recursion is something to avoid I am usually more interested in converting recursive solutions to not use recursion than the other way around. Maybe you want to do this task to make it easier to spot these dastardly recursive solutions.
Providing pseudo code will be difficult as the algorithm is so simple that the only thing that is tricky is the recursion.
I will leave the sort up to you. Know that the recursion for the sort works almost identical to the recursion for minindex. First you find the index of the smallest value and swap a[0] with a[smallest]. Repeat for a[1:] by calling the sort function recursively and increasing the start index. Eventually you will get to where the start index = length and you are done sorting.
One last note. Insertion sort is a replacement sort. It changes the order of element sin the original list. You will not be making any L2[] lists.
I don't know why you want a recursive sort. Recursion is something to avoid I am usually more interested in converting recursive solutions to not use recursion than the other way around. Maybe you want to do this task to make it easier to spot these dastardly recursive solutions.
Providing pseudo code will be difficult as the algorithm is so simple that the only thing that is tricky is the recursion.
function minindex(items, start, end): if start == end retrun start index = minindex(items, start + 1, end) <== The recursion if items[index] < items[start] return index else return startThis is a particularly stupid design. Not only is a non-recursive looping solution faster, but it is much easier to understand.
def minindex(a, i, n): min_ = i for i in range(i+1, n+1): if a[i] < a[min_]: min_ = i return min_The code is so simple that there really isn't any need for the function at all and the loop can be included directly in the sorting routine.
I will leave the sort up to you. Know that the recursion for the sort works almost identical to the recursion for minindex. First you find the index of the smallest value and swap a[0] with a[smallest]. Repeat for a[1:] by calling the sort function recursively and increasing the start index. Eventually you will get to where the start index = length and you are done sorting.
One last note. Insertion sort is a replacement sort. It changes the order of element sin the original list. You will not be making any L2[] lists.