병합 정렬 인덱스 오류 작동 원리

Question

def merge (seq, p, q, r): 
    # n1: length of sub-array [p..q] 
    n1 = q - p + 1 
    # n2: length of sub-array [q+1 ..r] 
    n2 = r - q 
    # Left and Right arrays 
    left_arr = [] 
    right_arr = [] 
    for i in xrange(0, n1): 
     left_arr.append(seq[p+i]) 
    for j in xrange(0, n2): 
     right_arr.append(seq[q+j+1]) 

    j=0 
    i=0 
    for k in xrange(p,r+1): 
     if left_arr[i]<= right_arr[j]: 
      seq[k]=left_arr[i] 
      i+=1 
     else: 
      seq[k]=right_arr[j] 
      j+=1 
    return seq 

s = [2,4,5,7,1,2,3,6] 
p = 0 
q = 3 
r = 7 
print merge(s,p,q,r) 

:

1. 의이 순서가 병합하는 인덱스 번호와 함께 촬영 된 분류되지 않은 순서. (p = 초기, R = 최종 Q = 중간)

2. 지금

   , left_arr 및 right_arr 우리 left_arr 및 right_arr 초기 값을 각각 [P, Q], [Q + 1, R]

3. 있다 (i = 0, j = 0). 우리는

위의 기능은 마지막 번호까지 정렬 할 수 있습니다 ... 우리가 정렬 된 값으로 서열의 값을 교체하는 반복하면서

"7"... 시퀀스 서열 반복 .. 결국 "IndexError"를 보여줍니다. 나는 그것을 잡아서 고치기 위해 예외 처리를 사용할 수 있지만, 나는 생각한다 ... 병합 정렬을 위해, 그것의 너무 많다. 누구든지 코드를 가능한 쉽게 수정하는 것을 도와 줄 수있다. 내가 알고리즘을 배우고

는 ... (책을 다음과 토마스 H 코만하여 알고리즘 소개)

Answer 1

문제는 마지막 반복에서 내가 4와 동일 할 것입니다 그리고 당신은 left_arr [5 액세스하려고 ] 존재하지 않습니다. i 또는 j가 해당 배열의 크기보다 커질 때 중지 조건을 추가 한 다음 다른 배열의 나머지 요소를 모두 seq에 추가해야합니다. 내가 코멘트 내가 코드를 편집 한 장소에 표시 한

def merge (seq, p, q, r): 
    # n1: length of sub-array [p..q] 
    n1 = q - p + 1 
    # n2: length of sub-array [q+1 ..r] 
    n2 = r - q 
    # Left and Right arrays 
    left_arr = seq[p:n1] #here 
    right_arr = seq[n1:r+1] #here 
    j=0 
    i=0 
    for k in xrange(p, r+1): 
     if left_arr[i]<= right_arr[j]: 
      seq[k]=left_arr[i] 
      i+=1 
      if i > n1-1: #here 
       break 
     else: 
      seq[k]=right_arr[j] #here 
      j+=1 
      if j > n2-1: 
       break 
    if i >= len(left_arr): #from here down 
     seq[k+1:] = right_arr[j:] 
    elif j >= len(right_arr): 
     seq[k+1:] = left_arr[i:] 

    return seq 

s = [2,4,5,7,1,1,1,1] 
p = 0 
q = 3 
r = 7 
print merge(s,p,q,r) 

: 여기

가 작동하는 코드입니다.

Answer 2

left_arr 및 right_arr을 반복하는 동안 배열 인덱스를 확인하지 않았습니다. 다른 배열이 끝나면 어느 한 배열의 왼쪽 부분을 병합해야합니다.

for k in xrange(p,r+1): 
    if left_arr[i]<= right_arr[j]: 
     seq[k]=left_arr[i] 
     i+=1 
    else: 
     seq[k]=right_arr[j] 
     j+=1 

    # --------------- add this ---------------- 
    # if any array ends, merge the left elements of the other array 
    if i >= len(left_arr): 
     seq[k:] = right_arr[j:] 
     break 
    elif j >= len(right_arr): 
     seq[k:] = left_arr[i:] 
     break 
    # --------------- end ---------------- 
return seq 

Answer 3

코드의 문제는 당신이 xrange(p, r+1) 전체를 반복하고 있다는, 그래서 약간의 반복에서 그 루프 중 하나 i 또는 j의 가치는 결국 IndexError의 원인이 len(left) 또는 len(right)의 값을 동일하게 할 수도 있습니다.

def merge(seq,p,q,r): 
    left=seq[p:q+1]  #a better way to fetch the list 
    right=seq[q+1:]  
    i=0 
    j=0 
    #you shuldn't loop over the length of seq as that might make the value of either i or j 
    # greater than the length of left or right lists respectively. 
    # so you should only loop until one of the lists is fully exhausted 

    while i<len(left) and j<len(right): 
     if left[i] <= right[j] : 
      seq[i+j]=left[i] 
      i+=1 
     else: 
      seq[i+j]=right[j] 
      j+=1 

    #now the while loop is over so either right or left is fully traversed, which can be 
    #find out my matching the value of j and i with lenghts of right and left lists respectively 

    if j == len(right): 
     seq[i+j:]=left[i:] #if right is fully traversed then paste the remaining left list into seq 
    elif i==len(left):  #this is just vice-versa of the above step 
     seq[i+j:]=right[j:] 
    print seq 

s = [2,4,5,7,1,2,3,6] 
p = 0 
q = 3 
r = 7 
merge(s,p,q,r) 

출력 :

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