재귀 선택 Python을 정렬

Question

다가올 질문에 재귀 선택 정렬이 있습니다.

def selsort(l): 
    """ 
    sorts l in-place. 
    PRE: l is a list. 
    POST: l is a sorted list with the same elements; no return value. 
    """      

l1 = list("sloppy joe's hamburger place") 
vl1 = l1 

print l1 # should be: """['s', 'l', 'o', 'p', 'p', 'y', ' ', 'j', 'o', 'e', "'", 's', ' ', 'h', 'a', 'm', 'b', 'u', 'r', 'g', 'e', 'r', ' ', 'p', 'l', 'a', 'c', 'e']""" 

ret = selsort(l1) 

print l1 # should be """[' ', ' ', ' ', "'", 'a', 'a', 'b', 'c', 'e', 'e', 'e', 'g', 'h', 'j', 'l', 'l', 'm', 'o', 'o', 'p', 'p', 'p', 'r', 'r', 's', 's', 'u', 'y']""" 
print vl1 # should be """[' ', ' ', ' ', "'", 'a', 'a', 'b', 'c', 'e', 'e', 'e', 'g', 'h', 'j', 'l', 'l', 'm', 'o', 'o', 'p', 'p', 'p', 'r', 'r', 's', 's', 'u', 'y']""" 

print ret # should be "None" 

나는 키 → l.sort(key=str.lower)를 사용하여이 작업을 얻는 방법을 알고있다. 그러나 문제는 최소한으로 대신 최대 요소를 추출하고 재귀 적으로 정렬 된 하위 목록에 .append(...)까지만 추출하기를 원합니다.

도움을받을 수 있다면 크게 감사하겠습니다.

Answer 1

정렬 방법은 원하는대로 수행해야합니다. 역방향을 원할 경우 list.reverse()를 사용하십시오.

작업이 자신의 정렬 방법을 만드는 것이라면 수행 할 수 있습니다.

아마 이런 식으로 뭔가를 시도 :

def sort(l): 
    li=l[:]          #to make new copy 
    newlist = []         #sorted list will be stored here 
    while len(li) != 0:       #while there is stuff to be sorted 
     bestindex = -1        #the index of the highest element 
     bestchar = -1        #the ord value of the highest character 
     bestcharrep = -1       #a string representation of the best character 
     i = 0 
     for v in li: 
      if ord(v) < bestchar or bestchar == -1:#check if string is lower than old best 
       bestindex = i      #Update best records 
       bestchar = ord(v) 
       bestcharrep = v 
      i += 1 
     del li[bestindex]       #delete retrieved element from list 
     newlist.append(bestcharrep)    #add element to new list 
    return newlist         #return the sorted list 

Answer 2

겠어요 - 문제를 이해합니까?

의 당신이해야했다 무엇을 살펴 보자 :

가 반복적으로 분류 하위 목록 만 (...)으로 .Append하는 대신 최소한의 그것을 최대의 요소를에서 추출합니다.

그래서, 우리는 다음과 같은 일을 수행

1) 최대의 요소를 추출합니다. 여기서 "추출"이 의미하는 것을 이해합니까? 최대 요소를 찾는 방법을 알고 있습니까?

2) 재귀 적으로 하위 목록을 정렬합니다. 여기서 "하위 목록"은 최대 요소를 추출한 후에 다른 모든 항목으로 구성됩니다. 재귀가 어떻게 작동하는지 알고 있습니까? 하위 목록을 사용하여 정렬 함수를 다시 호출하고 정렬을 사용하여 정렬을 수행합니다. 결국, 함수의 목적은리스트를 정렬하는 것입니다. 그래서 이것은 올바르게 작동 할 것입니다, 그렇죠? :)

3) .append() 하위 목록을 정렬 한 결과의 최대 요소. 이것은 어떤 설명도 요구해서는 안됩니다.

물론 재귀를위한 기본 사례가 필요합니다. 언제베이스 케이스가 있을까요? 우리가 쓰여진대로 정확하게 단계들을 따라갈 수 없을 때. 언제 그런 일이 일어 났습니까? 음, 왜일까요? 답변 : 요소가 없으면 최대 요소를 추출 할 수 없습니다. 추출 할 최대 요소가 없기 때문입니다.

따라서 함수의 시작 부분에서 빈 목록이 전달되었는지 확인합니다. 빈 목록을 정렬하면 빈 목록이 만들어지기 때문에 빈 목록 만 반환합니다. (왜 보이나요?) 그렇지 않으면 다른 단계를 밟습니다.