CODEWITHSUNDEEP
pythonrecursion
Saoish
Saoish

Reputation: 63

A recursive function to sort a list of ints

I want to define a recursive function can sort any list of ints:

def sort_l(l):
    if l==[]:
        return []
    else:
        if len(l)==1:
            return [l[-1]]
        elif l[0]<l[1]:
            return [l[0]]+sort_l(l[1:])
        else:
            return sort_l(l[1:])+[l[0]]

Calling this function on a list [3, 1, 2,4,7,5,6,9,8] should give me:

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

But I get:

print(sort_l([3, 1, 2,4,7,5,6,9,8]))--> [1, 2, 4, 5, 6, 8, 9, 7, 3]

Please help me to fix the problem, actual code would be appreciated. Thanks!

Upvotes: -2

Views: 26351

Answers (10)

chorcharg
chorcharg

Reputation: 1

Just index access, condition, and recursions:

def ordena(vector):

    if len(vector)==1:
        return vector
    
    if(vector[0]>vector[1]):
        vector[1], vector[0] = vector[0], vector[1]
        
    vector = vector[0:1] + ordena(vector[1:])
    
    return ordena(vector[:-1]) + vector[-1:]


v = [3,2,5,1,10,8,4]
print (v)
print(ordena(v))

Upvotes: 0

Niraj Kumar Singh
Niraj Kumar Singh

Reputation: 11

This is a recursive solution. For an explanation, refer to this video:

arr = [3,1,2,4,7,5,6,9,8]

def insert_fn(arr, temp):  # Hypothesis
    if len(arr) == 0 or arr[-1] <= temp:  # Base - condition
        arr.append(temp)
        return arr
         
    # Induction
    val = arr[-1]
    arr.pop()
    insert_fn(arr, temp)  # Call function on a smaller input.
    arr.append(val)  # Induction step
    return arr

def sort_fn(arr):  # Hypothesis
    if len(arr) == 1:  # Base - condition
        return arr
    
    # Induction
    val = arr[-1]  
    arr.pop()
    sort_fn(arr)  # Call function on a smaller input.
    insert_fn(arr, val) # Induction step
    return arr

print(sort_fn(arr))

Upvotes: 0

Will Be
Will Be

Reputation: 119

This is a complementary answer since both quicksort and complexity are already covered in previous answers. Although, I believe an easy-to-get sort function that covers Python's identity is missing*.

def sort(xs: list) -> list:
    if not xs:
        return xs
    else:
        xs.remove(num := min(xs))
        return [num] + sort(xs)

[*] Python is a (slow) interpreted language, but it has become famous because of its readability and easiness to learn. It doesn't really "reward" its developers for using immutable objects nor it is a language that should be used for computation intensive applications

Upvotes: 0

Drlight Dr
Drlight Dr

Reputation: 9

def maximum(lis):
    if len(lis) == 1:
        return lis[0]
    return maximum(lis[1:]) if lis[0] < lis[1] else maximum(lis[:1] + lis[2:])

def sorter(lis):
    if len(lis) == 1:
        return lis
    x = maximum(lis)
    lis.remove(x)
    return sorter(lis) + [x]

with functional programming:

sor = lambda lis: lis if len(lis) == 1 else [lis.pop(lis.index(reduce(lambda x, y: x if x > y else y, lis)))] + sor(lis)

Upvotes: 1

Akoffice
Akoffice

Reputation: 381

Here i am explaining recursive approach to sort a list. we can follow "Induction Base-condition Hypothesis" recursion approach. so basically we consider our hypothesis here sort_l(nums) function which sorts for given list and Base condition will be found when we have singly number list available which is already sorted. Now in induction step, we insert the temp element (last element of list) in the correct position of given list.
example-

  1. sort_l([1,5,0,2]) will make below recursively call
  2. sort_l([1]) <-- 5 (here you need to insert 5 in correct position)
  3. sort_l([1,5]) <-- 0 (here you need to insert 0 in correct position)
  4. sort_l([0,1,5]) <-- 2 (here you need to insert 2 in correct position)
  5. sort_l([0,1,5,2]) Finally it will be in sorted list.

====== Below is working code=======

def insert_element(nums, temp):
    if len(nums) == 1:
        if nums[0] > temp:
            nums.insert(0, temp)
        elif nums[0] < temp:
            nums.append(temp)
    else:
        for i in range(len(nums)):
            if nums[i] > temp:
                nums.insert(i, temp)
                break
        if nums[-1] < temp:
            nums.append(temp)


def sort_l(nums): ## hypothesis
    if len(nums)==1: ## base condition
        return nums
    temp = nums[-1]
    nums.pop()
    sort_l(nums)
    insert_element(nums, temp) ## induction
    return nums

Upvotes: 0

laxman dangi
laxman dangi

Reputation: 1

#sort an int list using recursion

global array
array=[5,3,8,4,2,6,1]
def sort1(array:[])->[]:
    if len(array)==1:
        return 
    temp=array[-1]
    array.pop()
    sort1(array)
    sort2(array,temp)
def sort2(array:[],temp):
    if len(array)==0 or temp>=array[-1]:
        array.append(temp)
        return
    a=array[-1]
    array.pop()
    sort2(array,temp)
    array.append(a)
sort1(array)
print(array)

Upvotes: 0

Brewyn
Brewyn

Reputation: 1

def sort(array, index = 0, bigNumber = 0):
  if len(array) == index:
    return array

  elif bigNumber > array[index]:
    array[index - 1] = array[index]
    array[index] = bigNumber
    bigNumber = array[0]
    index = 0

  else:
    bigNumber = array[index]

  return sort(array, (index + 1), bigNumber)

Upvotes: 0

Sohaib Omar
Sohaib Omar

Reputation: 133

def quicksort(lst):
    "Quicksort over a list-like sequence"
    if len(lst) == 0:
        return lst
    pivot = lst[0]
    pivots = [x for x in lst if x == pivot]
    small = quicksort([x for x in lst if x < pivot])
    large = quicksort([x for x in lst if x > pivot])
    return small + pivots + large

Above is a more readable recursive implementation of Quick Sort Algorithm. Above piece of code is from book Functional programing in python by O'REILLY.
Above function will produce.

list=[9,8,7,6,5,4]
quicksort(list)
>>[4,5,6,7,8,9]

Upvotes: 0

Thibaut
Thibaut

Reputation: 1408

The quick sort is recursive and easy to implement in Python:

def quick_sort(l):
    if len(l) <= 1:
        return l
    else:
        return quick_sort([e for e in l[1:] if e <= l[0]]) + [l[0]] +\
            quick_sort([e for e in l[1:] if e > l[0]])

will give:

>>> quick_sort([3, 1, 2, 4, 7, 5, 6, 9, 8])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Upvotes: 7

Charles Hetterich
Charles Hetterich

Reputation: 181

For this you would want to use merge sort. Essentially in a merge sort you recursively split the list in half until you have single elements and than build it back up in the correct order. merge sort on has a complexity of O(n log(n)) and is an extremely stable sorting method.

Here are some good in depth explanations and visuals for merge sorting:

Upvotes: 1

Related Questions