##### Combine Two Recursive Functions To Create One Recursive Selection Sort Function
 Combine Two Recursive Functions To Create One Recursive Selection Sort Function Jeremy7 Programmer named Tim Posts: 10 Threads: 2 Joined: Jan 2021 Reputation: Jan-13-2021, 10:04 AM (This post was last modified: Jan-13-2021, 10:04 AM by 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)) Reply Serafim Lumberjack Posts: 101 Threads: 0 Joined: Jan 2021 Reputation: Jan-13-2021, 10:43 PM (This post was last modified: Jan-13-2021, 10:43 PM by Serafim. Edit Reason: Corrected my english ) 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 Jeremy7 Programmer named Tim Posts: 10 Threads: 2 Joined: Jan 2021 Reputation: Jan-13-2021, 11:07 PM (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 deanhystad Weighs the Same as a Duck Posts: 4,246 Threads: 16 Joined: Feb 2020 Reputation: 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. ```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 Serafim Lumberjack Posts: 101 Threads: 0 Joined: Jan 2021 Reputation: Jan-14-2021, 07:49 PM (This post was last modified: Jan-14-2021, 07:49 PM by Serafim. Edit Reason: Removed part of the answer as I was wrong in that part. ) (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 deanhystad Weighs the Same as a Duck Posts: 4,246 Threads: 16 Joined: Feb 2020 Reputation: Jan-14-2021, 08:33 PM 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 Serafim Lumberjack Posts: 101 Threads: 0 Joined: Jan 2021 Reputation: Jan-14-2021, 09:20 PM 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 Serafim Lumberjack Posts: 101 Threads: 0 Joined: Jan 2021 Reputation: Jan-14-2021, 09:50 PM (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 Jeremy7 Programmer named Tim Posts: 10 Threads: 2 Joined: Jan 2021 Reputation: Jan-14-2021, 11:43 PM (This post was last modified: Jan-15-2021, 09:58 PM by Jeremy7.) (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! ```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 Serafim Lumberjack Posts: 101 Threads: 0 Joined: Jan 2021 Reputation: Jan-15-2021, 08:47 AM (This post was last modified: Jan-15-2021, 08:48 AM by Serafim.) (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 python create function validation mg24 1 177 Nov-15-2022, 01:57 AM Last Post: deanhystad create my exception to my function korenron 2 144 Nov-09-2022, 01:50 PM Last Post: korenron Create a function for writing to SQL data to csv mg24 4 320 Oct-01-2022, 04:30 AM Last Post: mg24 Create SQL connection function and validate mg24 1 221 Sep-30-2022, 07:45 PM Last Post: deanhystad a.sort() == b.sort() all the time 3lnyn0 1 558 Apr-19-2022, 06:50 PM Last Post: Gribouillis list sort() function bring backs None CompleteNewb 6 1,409 Mar-26-2022, 03:34 AM Last Post: Larz60+ Why recursive function consumes more of processing time than loops? M83Linux 9 2,870 May-20-2021, 01:52 PM Last Post: DeaD_EyE Is there a library for recursive object creation using config objects johsmi96 0 1,337 May-03-2021, 08:09 PM Last Post: johsmi96 Sort Function: <' not supported between instances of 'float' and 'tuple' quest 2 5,646 Apr-30-2021, 07:37 PM Last Post: quest BST insert using recursive hichipi12 4 2,048 Feb-19-2021, 09:23 PM Last Post: hichipi12

Forum Jump:

### User Panel Messages

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