Python Forum
Combine Two Recursive Functions To Create One Recursive Selection Sort Function
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Combine Two Recursive Functions To Create One Recursive Selection Sort Function
#1
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))
Reply
#2
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 likes this post
Reply
#3
(Jan-13-2021, 10:43 PM)Serafim Wrote: 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.
Reply
#4
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.
Reply
#5
(Jan-14-2021, 07:49 AM)deanhystad Wrote: 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
Jeremy7 likes this post
Reply
#6
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.
Reply
#7
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).
Reply
#8
(Jan-14-2021, 08:33 PM)deanhystad Wrote: 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.
ndc85430 likes this post
Reply
#9
(Jan-14-2021, 07:49 PM)Serafim Wrote: [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! Smile

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))
Reply
#10
(Jan-14-2021, 11:43 PM)Jeremy7 Wrote: Your my go-to guy for coding!
Thank you! Happy to have been of some help.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
Photo a.sort() == b.sort() all the time 3lnyn0 1 456 Apr-19-2022, 06:50 PM
Last Post: Gribouillis
  list sort() function bring backs None CompleteNewb 6 993 Mar-26-2022, 03:34 AM
Last Post: Larz60+
  Why recursive function consumes more of processing time than loops? M83Linux 9 2,731 May-20-2021, 01:52 PM
Last Post: DeaD_EyE
  Is there a library for recursive object creation using config objects johsmi96 0 1,273 May-03-2021, 08:09 PM
Last Post: johsmi96
  Sort Function: <' not supported between instances of 'float' and 'tuple' quest 2 5,219 Apr-30-2021, 07:37 PM
Last Post: quest
  BST insert using recursive hichipi12 4 1,872 Feb-19-2021, 09:23 PM
Last Post: hichipi12
  Execution of Another Recursive Function muzikman 5 1,796 Dec-04-2020, 08:13 PM
Last Post: snippsat
  Don't Understand Recursive Function muzikman 9 2,259 Dec-03-2020, 05:10 PM
Last Post: muzikman
  list call problem in generator function using iteration and recursive calls postta 1 1,167 Oct-24-2020, 09:33 PM
Last Post: bowlofred
  Recursive function returns None, when True is expected akar 0 2,434 Sep-07-2020, 07:58 PM
Last Post: akar

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020