파이썬 내 목록을 뒤섞고있다

Question

파이썬에서 목록을 사용하여 병합 정렬 알고리즘을 구현하려고합니다. 병합 코드가 괜찮습니다. (지금 당장 쓰지는 않겠지 만, 내게 묻기 만하면 행복하게 게시 할 수 있습니다.) 그러나 위의 재귀 적 수준으로 돌아 오면 목록이 섞여서 모르겠습니다. 왜. 병합 정말 좋은 것을

array 1: [56] 
array 2: [96] 
merged array: [56, 96] # the merge is fine 

array 1: [76] 
array 2: [73] 
merged array: [73, 76] # here too 

공지 사항 : 설명하기

,이 일어나고있는 무슨이다. 그러나, 통지 또한 다음 섹션에서 '어레이 (2)가'셔플되어

가

array 1: [56, 96] 
array 2: [76, 73]   # this is broken 
merged array: [56, 76, 73, 96] 

그것은 재귀 실행을 통해 무작위로 발생하는 (이론적으로 동일 [73, 76]와 같은 목록 위이다). 이 오류가 내 코드에없는 것을 과시, 배열 1이 아닌 배열이 발생하는 것이 여기에 주목 :

array 1: [96] 
array 2: [34] 
merged array: [34, 96] 

array 1: [19] 
array 2: [34] 
merged array: [19, 34] 

array 1: [96, 34]   # this is broken too 
array 2: [19, 34] 
merged array: [19, 34, 96, 34] 

이 방법, 나는 지금이 병합 정렬을 사용하여 목록을 주문할 수 없습니다. 파이썬의 목록이 정렬 된 순서라면, 왜 이런 일이 일어나는지 알 수 있습니까?

이

def merge_sort(array): 
    if len(array) > 1: 
     array1, array2 = partition(array) 
     merge_sort(array1) 
     merge_sort(array2) 
     array = merge(array1, array2) 
    return array 

def partition(array): 
    n = len(array)/2 
    array1 = array[0:n] 
    array2 = array[n::] 

    return array1, array2 

def merge(a, b): 
    array = [] 
    while len(a) > 0 or len(b) > 0: 
     if len(a) > 0 and len(b) > 0: 
      if a[0] <= b[0]: 
       array.append(a.pop(0)) 
      else: 
       array.append(b.pop(0)) 
     elif len(a) > 0: 
      array.append(a.pop(0)) 
     elif len(b) > 0: 
      array.append(b.pop(0)) 
    return array 

Answer 1

병합 정렬은 나누기 등-impera 알고리즘 :

요청으로

, 여기에 코드입니다 당신이 결합 후 다른 하위 문제에서 문제가합니다 (분할 부분)을 깨고 문제 해결책을 생성하는 서브 솔루션 (impera 부분).

병합 정렬에서 나누는 부분은 목록에서 생성 된 두 개의 하위 목록을 주문하는 것입니다. impera 부분은이 두 개의 을 서브 목록으로 정렬하고 고유 한 순차 목록에 병합합니다. 당신이 호출 할 때 : 병합 기능은 하위 목록이 주문 될 것으로 예상하여 impera 부분이기 때문에

merge([56, 96], [76, 73]) 

이 작동하지 않을 수 있습니다. 정렬 된 하위 목록을 유지하지 않으므로 코드가 작동하지 않지만 배열을 내부 정렬하지 않기 때문에 코드를 버리고 있습니다. 대신에 :

merge_sort(array1) 

당신이 있어야합니다

array1 = merge_sort(array1) 

을 그렇지 않으면 당신이 호출 할 때 :

merge(array1, array2) 

을 하위 목록이 정렬되지 않습니다.