병합 정렬, 하위 목록은 어디에 저장됩니까?

Question

나는 내가 사용하고있는 코드를 포함시켰다.

단일 값이있을 때까지 코드 시작으로 하위 목록이 계속 분할된다는 것을 알고 있습니다. 단일 값은 lefthalf 및 righthalf 변수에 저장되고 정렬 된 순서로 병합됩니다.

두 코드의 두 목록을 병합하는 방법은 무엇입니까? 알겠지만이 하위 목록은 alist라고하는 별도의 로컬 변수에 저장됩니다. 어떻게 병합됩니까?

def mergeSort(alist): 

    if len(alist)>1: 
     mid = len(alist)//2 
     lefthalf = alist[:mid] 
     righthalf = alist[mid:] 

     mergeSort(lefthalf) 
     mergeSort(righthalf) 

     i=0 
     j=0 
     k=0 

     while i < len(lefthalf) and j < len(righthalf): 
      if lefthalf[i] < righthalf[j]: 
       alist[k]=lefthalf[i] 
       i=i+1 
      else: 
       alist[k]=righthalf[j] 
       j=j+1 
      k=k+1 


     while i < len(lefthalf): 
      alist[k]=lefthalf[i] 
      i=i+1 
      k=k+1 


     while j < len(righthalf): 
      alist[k]=righthalf[j] 
      j=j+1 
      k=k+1 

Answer 1

첫 번째 while 루프는 두 개의리스트 중 하나가 소진 될 때까지 lefthalf, righthalf에서 작은 작은 항목을 선택합니다. 제 while 루프 복사본 alist 남은 항목 (lefthalf, righthalf 각각 정렬 된 항목 포함)

while i < len(lefthalf) and j < len(righthalf): 
    if lefthalf[i] < righthalf[j]: 
     # Pick the smallest item from `leftHalf` if has a smaller item 
     alist[k]=lefthalf[i] 
     i=i+1 
    else: 
     # Pick smallest item from `rightHalf` 
     alist[k]=righthalf[j] 
     j=j+1 
    k = k + 1 
    # `k` keeps track position of `alist` 
    # (where to put the smallest item) 
    # Need to increase the `k` for the next item 

번째. 두 개의 루프 본문 중 하나만 실행됩니다. 하나는 첫 번째 while 루프에서 제외됩니다.

---

SIDE 참고 : 장소에 alist의 항목을 변경 alist[k] = ....

Answer 2

따라서이 목록 버전은 mergeSort의 inplace 버전으로, 목록을 받아서 정렬 된 버전으로 수정합니다. (각 절반의 복사본을 만드는 것이 포함되어 있으므로 일정한 공간이 아닙니다.) 여기서 코드가 수행하는 작업에 대해 주석을 달았습니다.

def mergeSort(alist): 

    if len(alist)>1: # empty lists and lists of one element are sorted already 
     mid = len(alist)//2 # find the halfway point 
     lefthalf = alist[:mid] # make a copy of the first half of the list 
     righthalf = alist[mid:] # make a copy of the second half of the list 

     mergeSort(lefthalf) 
     mergeSort(righthalf) 

     # Each half is now sorted 

     # Now we're going to copy elements from lefthalf and righthalf 
     # back into alist. We do this by keeping three index variables: 
     # where we are in lefthalf (i), where we are in righthalf (j) 
     # and where we are going to put stuff in alist (k) 

     i=0 
     j=0 
     k=0 

     while i < len(lefthalf) and j < len(righthalf): 
      # that is, "while we still have stuff left in both halves": 

      if lefthalf[i] < righthalf[j]: 
       # The thing we're looking at in lefthalf is smaller 
       # than what we have in righthalf. Copy the thing in 
       # lefthalf over to alist, and increment i 
       alist[k]=lefthalf[i] 
       i=i+1 
      else: 
       # same story, but on the right half 
       alist[k]=righthalf[j] 
       j=j+1 
      k=k+1 


     # If we ran out of stuff in righthalf first, finish up copying 
     # over all the rest of the stuff in lefthalf 
     while i < len(lefthalf): 
      alist[k]=lefthalf[i] 
      i=i+1 
      k=k+1 


     # If we ran out of stuff in lefthalf first, finish up copying 
     # over all the rest of the stuff in righthalf 
     while j < len(righthalf): 
      alist[k]=righthalf[j] 
      j=j+1 
      k=k+1 

     # Note that only one of those while loops will actually do anything - 
     # the other while loop will have its condition false the first time