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.