Combine Two Recursive Functions To Create One Recursive Selection Sort Function

[Jeremy7]

This is just a personal project I'm working on, and have been working on it for days, looking at several Recursive Selection Sort functions online to help me accomplish this goal, but to no avail because the Recursive Selection Sort functions I've come across did not help. I would like to combine the two (2) Recursive functions below to create one (1) Recursive Selection Sort function, using a 'while loop' and the same variables as much as possible. Please provide the pseudo code; I'd like to try to figure it out from pseudo code to test the knowledge I've attained thus far in learning the Python programming language. Oh and, I'm aware of the Selection sorting shortcut, the sort() function, but I want to learn the long way as well in how to code functions, programs and processes. Thanks!

def searchMinFromList(L,n):
    minValue = L[0]
    idx = 0
    counter = 1

    while (counter < n):
        v = L[counter]
        if v < minValue:
            minValue = v
            idx = counter

        else:
            pass

        counter += 1

    return minValue, idx


def sortList(L,n):
    L2 = []
    counter = 0

    while (counter < n):
        m, idx = searchMinFromList(L,n)
        L2.append(m)
        del L[idx]
        n-=1

    return L2

L = [34, -1, 0, 89, 21, -40, 7]
n = len(L)

print(sortList(L, n))

[Serafim]

Selection sort is not really fit for recursive algorithms as the easiest way to perform a selection sort is really by
two loops, but of course it is doable.
Edit: When rereading your post I find that this is the version closest to your idea:
This one I used as an example in functional programming:
Start with the list to sort e.g. list_to_sort = [2, 4, 1, 6, 11, 3, 4, 7, 9, 8] and result = an empty list then
while there still is at least one element in the list_to_sort
find the smallest element in the list, remove it and add it to the empty list and call the sort function again

def sort(list_to_sort, result):
    print(list_to_sort, result) # Just to show what happens
    if not(list_to_sort):       # An empty list equals False here
        return result
    min_element = find_the_smallest_element(list_to_sort)
    result.append(min_element)
    list_to_sort.remove(min_element)
    return sort(list_to_sort, result)

Call with:

print(sort([2, 4, 1, 6, 11, 3, 4, 7, 9, 8], []))

A run where all printouts except for the last one is from inside the function:

[2, 4, 1, 6, 11, 3, 4, 7, 9, 8] []
[2, 4, 6, 11, 3, 4, 7, 9, 8] [1]
[4, 6, 11, 3, 4, 7, 9, 8] [1, 2]
[4, 6, 11, 4, 7, 9, 8] [1, 2, 3]
[6, 11, 4, 7, 9, 8] [1, 2, 3, 4]
[6, 11, 7, 9, 8] [1, 2, 3, 4, 4]
[11, 7, 9, 8] [1, 2, 3, 4, 4, 6]
[11, 9, 8] [1, 2, 3, 4, 4, 6, 7]
[11, 9] [1, 2, 3, 4, 4, 6, 7, 8]
[11] [1, 2, 3, 4, 4, 6, 7, 8, 9]
[] [1, 2, 3, 4, 4, 6, 7, 8, 9, 11]
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11]

Printout with your list:

print(sort([34, -1, 0, 89, 21, -40, 7], []))
[34, -1, 0, 89, 21, -40, 7] []
[34, -1, 0, 89, 21, 7] [-40]
[34, 0, 89, 21, 7] [-40, -1]
[34, 89, 21, 7] [-40, -1, 0]
[34, 89, 21] [-40, -1, 0, 7]
[34, 89] [-40, -1, 0, 7, 21]
[89] [-40, -1, 0, 7, 21, 34]
[-40, -1, 0, 7, 21, 34, 89]

Another idea (which was my first attempt, before carefully reading your post):
Start with the list to sort e.g. list_to_sort = [2, 4, 1, 6, 11, 3, 4, 7, 9, 8] and the position of the first element to sort in,
which of course has position 0 and
find the position (min_pos) of the smallest element in the list,
swap the elements on positions pos and min_pos and recurse with the list and the next position.
stop if pos has reached the last position. Observe that the last swap puts both the last and
the next to the last elements in place:

def sort(list_to_sort, pos):
    if pos == "last position in the list": # Then its complete, the last element
                                           # was of course swapped in place already
        return list_to_sort
    print(list_to_sort, pos)               # Just to show what happens
    min_pos = find_the_position of_the_smallest_element(list_to_sort)
    swap_elements_on_positions(pos, min_pos)
    return sort(list_to_sort, pos + 1)

Call with:

print(sort([2, 4, 1, 6, 11, 3, 4, 7, 9, 8], 0))

A run where all printouts except for the last one is from inside the function:

[2, 4, 1, 6, 11, 3, 4, 7, 9, 8] 0
[1, 4, 2, 6, 11, 3, 4, 7, 9, 8] 1
[1, 2, 4, 6, 11, 3, 4, 7, 9, 8] 2
[1, 2, 3, 6, 11, 4, 4, 7, 9, 8] 3
[1, 2, 3, 4, 11, 6, 4, 7, 9, 8] 4
[1, 2, 3, 4, 4, 6, 11, 7, 9, 8] 5
[1, 2, 3, 4, 4, 6, 11, 7, 9, 8] 6
[1, 2, 3, 4, 4, 6, 7, 11, 9, 8] 7
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11] 8
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11]

[Jeremy7]

Selection sort is not really fit for recursive algorithms as the easiest way to perform a selection sort is really by
two loops, but of course it is doable.
Edit: When rereading your post I find that this is the version closest to your idea:
This one I used as an example in functional programming:
Start with the list to sort e.g. list_to_sort = [2, 4, 1, 6, 11, 3, 4, 7, 9, 8] and result = an empty list then
while there still is at least one element in the list_to_sort
find the smallest element in the list, remove it and add it to the empty list and call the sort function again

def sort(list_to_sort, result):
    print(list_to_sort, result) # Just to show what happens
    if not(list_to_sort):       # An empty list equals False here
        return result
    min_element = find_the_smallest_element(list_to_sort)
    result.append(min_element)
    list_to_sort.remove(min_element)
    return sort(list_to_sort, result)

Call with:

print(sort([2, 4, 1, 6, 11, 3, 4, 7, 9, 8], []))

A run where all printouts except for the last one is from inside the function:

[2, 4, 1, 6, 11, 3, 4, 7, 9, 8] []
[2, 4, 6, 11, 3, 4, 7, 9, 8] [1]
[4, 6, 11, 3, 4, 7, 9, 8] [1, 2]
[4, 6, 11, 4, 7, 9, 8] [1, 2, 3]
[6, 11, 4, 7, 9, 8] [1, 2, 3, 4]
[6, 11, 7, 9, 8] [1, 2, 3, 4, 4]
[11, 7, 9, 8] [1, 2, 3, 4, 4, 6]
[11, 9, 8] [1, 2, 3, 4, 4, 6, 7]
[11, 9] [1, 2, 3, 4, 4, 6, 7, 8]
[11] [1, 2, 3, 4, 4, 6, 7, 8, 9]
[] [1, 2, 3, 4, 4, 6, 7, 8, 9, 11]
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11]

Printout with your list:

print(sort([34, -1, 0, 89, 21, -40, 7], []))
[34, -1, 0, 89, 21, -40, 7] []
[34, -1, 0, 89, 21, 7] [-40]
[34, 0, 89, 21, 7] [-40, -1]
[34, 89, 21, 7] [-40, -1, 0]
[34, 89, 21] [-40, -1, 0, 7]
[34, 89] [-40, -1, 0, 7, 21]
[89] [-40, -1, 0, 7, 21, 34]
[-40, -1, 0, 7, 21, 34, 89]

Another idea (which was my first attempt, before carefully reading your post):
Start with the list to sort e.g. list_to_sort = [2, 4, 1, 6, 11, 3, 4, 7, 9, 8] and the position of the first element to sort in,
which of course has position 0 and
find the position (min_pos) of the smallest element in the list,
swap the elements on positions pos and min_pos and recurse with the list and the next position.
stop if pos has reached the last position. Observe that the last swap puts both the last and
the next to the last elements in place:

def sort(list_to_sort, pos):
    if pos == "last position in the list": # Then its complete, the last element
                                           # was of course swapped in place already
        return list_to_sort
    print(list_to_sort, pos)               # Just to show what happens
    min_pos = find_the_position of_the_smallest_element(list_to_sort)
    swap_elements_on_positions(pos, min_pos)
    return sort(list_to_sort, pos + 1)

Call with:

print(sort([2, 4, 1, 6, 11, 3, 4, 7, 9, 8], 0))

A run where all printouts except for the last one is from inside the function:

[2, 4, 1, 6, 11, 3, 4, 7, 9, 8] 0
[1, 4, 2, 6, 11, 3, 4, 7, 9, 8] 1
[1, 2, 4, 6, 11, 3, 4, 7, 9, 8] 2
[1, 2, 3, 6, 11, 4, 4, 7, 9, 8] 3
[1, 2, 3, 4, 11, 6, 4, 7, 9, 8] 4
[1, 2, 3, 4, 4, 6, 11, 7, 9, 8] 5
[1, 2, 3, 4, 4, 6, 11, 7, 9, 8] 6
[1, 2, 3, 4, 4, 6, 7, 11, 9, 8] 7
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11] 8
[1, 2, 3, 4, 4, 6, 7, 8, 9, 11]

Thanks, Serafim! Your code is much simpler than what I was attempting to do. Basically, what I was attempting to do was to add the necessary code to the 'def searchMinFromList()' recursive function from the 'def sortList()' recursive function to convert the 'def searchMinFromList()' recursive function to a recursive selection sort function. Is that at all possible? Thanks for your help.

[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.

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 start

This 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.

[Serafim]

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.

I don't at all agree to your statement that "Recursion is something to avoid"

1. Jeremys request is an idea for how to combine his two functions into one that uses recursion.

2. He misses the point in calling his functions recursive, which they obviously are not but his request is nonetheless understandable, recursion is in itself interesting and often leads to shorter solutions than their iterative counterparts but they tend to be harder to debug.

3. In functional programming languages recursion is the only option for repetitive tasks. My examples are taken from my lectures (on the functional programming language Scheme) and transformed to Python, which in itself was an interesting task.

4. Also, when looking at the results, it is simple thinking behind: "How do we take one step towards a solution and how do we know when to stop?"

In the first solution, (a) pick the smallest element from the list and add it to the (initially empty) solution and (b) stop when there are no more elements.

In the second: (a) point at the next place (initially the first) to put the smallest remaining element (to make extra space unnecessary I use the "vacant" place as storage, hence the swap) and (b) stop when we have reached the last place.

In my mind it leads to elegant solutions and not "bastardly" (I guess that "dastardly" is a mistake) even if I still think that an iterative solution is more intuitive (following Jeremys idea of how to sort the elements into a new list):

def selection_sort(lst):
    result = []
    while lst:
        element = lst[0]
        for i in range(1, len(lst)):
            if lst[i] < element:
                element = lst[i]
        lst.remove(element)
        result.append(element)
    return result

[deanhystad]

dastardly is "evil, wicked, cruel". Recursion is dastardly. The solutions are often far from being efficient or understandable. Recursive solutions often have restrictions that cause them to fail for some data sets while working fine for others (recursion depth). Recursion is difficult to debug.

Sometimes a recursive solution is a good solution, but that is just not the case with an insertion sort.

[Serafim]

Note: Your functions are iterative, not recursive. @deanhystad is right there. A recursive function to find the smallest element in your list would, as @deanhystad pointed out, call itself, like this implementation of "find_the_smallest_element" (from my first solution):

def find_the_smallest_element(lst):
    def inner(lst, el):
        if not lst:
            return el
        elif lst[0] < el:
            return inner(lst[1:], lst[0])
        else:
            return inner(lst[1:], el)

Where the recursion takes place in the embedded function "inner", still the same simplicity: (a) how do we take a step to a solution and (b) how do we know when to stop (even if the stop condition mostly occurs as the first branch).

[Serafim]

dastardly is "evil, wicked, cruel". Recursion is dastardly. The solutions are often far from being efficient or understandable. Recursive solutions often have restrictions that cause them to fail for some data sets while working fine for others (recursion depth). Recursion is difficult to debug.

Sometimes a recursive solution is a good solution, but that is just not the case with an insertion sort.

Recursion depth might be a problem, but only under special circumstances. As I pointed out, recursive solutions are often simple: "how do we take one (more) step towards a solution and how do we know when to stop?"
Also, some problems are natural to solve with recursion and others can not be (easily) solved with iteration. Quicksort, mergesort, depth-first search (like binary tree search) are some examples where recursion is much more efficient than iteration (apart from memory usage). The round-off algorithms for floating number operations are often recursive divide-and-conquer algorithms as they generally provide better results than the iterative ones.
So, even if you don't like recursion and even if recursive solutions sometimes are hard to understand and debug, recursion is important and thus important to study.

[Jeremy7]

[quote='deanhystad' pid='135130' dateline='1610610557']
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.

I don't at all agree to your statement that "Recursion is something to avoid"

1. Jeremys request is an idea for how to combine his two functions into one that uses recursion.

2. He misses the point in calling his functions recursive, which they obviously are not but his request is nonetheless understandable, recursion is in itself interesting and often leads to shorter solutions than their iterative counterparts but they tend to be harder to debug.

3. In functional programming languages recursion is the only option for repetitive tasks. My examples are taken from my lectures (on the functional programming language Scheme) and transformed to Python, which in itself was an interesting task.

4. Also, when looking at the results, it is simple thinking behind: "How do we take one step towards a solution and how do we know when to stop?"

In the first solution, (a) pick the smallest element from the list and add it to the (initially empty) solution and (b) stop when there are no more elements.

In the second: (a) point at the next place (initially the first) to put the smallest remaining element (to make extra space unnecessary I use the "vacant" place as storage, hence the swap) and (b) stop when we have reached the last place.

In my mind it leads to elegant solutions and not "bastardly" (I guess that "dastardly" is a mistake) even if I still think that an iterative solution is more intuitive (following Jeremys idea of how to sort the elements into a new list):

def selection_sort(lst):
    result = []
    while lst:
        element = lst[0]
        for i in range(1, len(lst)):
            if lst[i] < element:
                element = lst[i]
        lst.remove(element)
        result.append(element)
    return result

Thanks again, Serafim; your code is pretty much right on what I was aiming for! Okay, so not all functions in Python that begin with "def" are recursive functions; I'm learning. What I should have done to make answering my question a whole lot easier was to take the code from the 2 "def" functions I initially posted, like I did in the code you see below, and ask how I would tweak it just enough to make it work while still looking a little the same. Sorry about that.
Again, thanks! You're my go-to guy for coding!

def sortList(L,n):
    minValue = L[0]
    L2 = []
    idx = 0
    counter = 0
	
    while (counter < n):
        v = L[counter]
        if v < minValue:
            minValue = v
            idx = counter
            L2.append(minValue)
            del L[idx]
            n-=1

        counter += 1

    return L2

L = [34, -1, 0, 89, 21, -40, 7]
n = len(L)

print(sortList(L, n))

[Serafim]

Your my go-to guy for coding!

Thank you! Happy to have been of some help.