재귀를 사용하여 삽입 정렬을 구현하는 방법과 더 효율적인 방법은 무엇입니까?

Question

재귀를 사용하여 어떻게 구현할 수 있습니까? 더 효과적입니까?

내 코드 : 루프 for x in range(a,b): Body에 대한

def insertionSort(array): 
    '''(list) - > list 
    Returns a sorted list of integers by implementing 
    the insertion sort which returns numbers in array from 
    least to greatest 
    ''' 
    for i in range(1, len(array)): 

     if array[i-1] > array[i]: #Finds a number out of place 
      temp = array[i] 
      for a in range(0,i): 
       if temp < array[a]: 
        array.insert(a,temp) 
        del array[i+1] 
        break 
    return array 

Answer 1

모든이 꼬리 재귀로 재 구현 될 수있다 : 이것은한다고

def rfor(b, x = a): 
    if a < b: 
    Body 
    rfor(b, x + 1) 

대답을 직접 얻을만큼 당신을 줄 수 있습니다. 표준 파이썬에서 이것은 분명히 루프보다 느리고 반복마다 하나의 스택 프레임을 먹습니다. 꼬리 전화 최적화 기능이 우수한 다른 언어 및 구현에서는 비용이 동일 해집니다. 외관상으로는 Guido has said he's uninterested in tail call optimization.

Answer 2

간단한 재귀 버전 :

def insertionSort(array,i=1): 
    if i >= len(array): 
    return array 
    if array[i-1] > array[i]: 
    temp = array[i] 
    for a in range(0, i): 
     if temp < array[a]: 
     array.insert(a,temp) 
     del array[i+1] 
     break 
    return insertionSort(array, i+1) 

일반적으로 재귀는 나무와 연결리스트와 같은 특정 데이터 구조에 대한 더 좋다. 때로는 문제를 해결하기 위해 재귀를 생각하는 것이 더 쉽습니다. 재귀가 실제로 효율성을 위해 사용 된 경우는 기억이 안납니다.