잘못된 병합 정렬 결과

Question

나는 정규 병합 정렬 코드를 작성 했으므로이 함수를 'asize'와 숫자가 아닌 recieving 함수로 호출하면됩니다. 1 2 3 4 5 6 7 8 9 10] 는 일반 정렬 된 배열 난 [-858993460 1 2 3 4 5 6 7 8 9]

당신은을 통해 스테핑있어이

void merge_sort(int *a,int first, int last) 
{ 
    int middle; 
      if(first < last) 
      { 
       middle=(first+last)/2; 
       merge_sort(a,first,middle); 
       merge_sort(a,middle+1,last); 
       merge(a,first,middle,last); 
      } 
} 






void main() 
{ 

    int a[] = {9, 7, 2, 3, 5, 4, 1, 8, 6, 10}; 
    int asize= (sizeof a/sizeof a[0]); 
    merge_sort(a, 0, asize); 
For (i = 0; i < 10; i++) 
     printf ("%d ", a[i]); 

Answer 1

는 대부분의 경우는 asize - 1보다는 마지막 요소의 인덱스로 asize 통과 될 가능성이 off-by-one 오류입니다.

병합 정렬에 필요한 매개 변수는 첫 번째 및 마지막 인덱스 (0부터 시작 함)이므로 크기가 10 인 배열의 경우 0 및 9이됩니다. 0 및 10을 현재 코드로 전달 중입니다. 이 때문에

, 당신은 실제로 "배열"정렬하고 있습니다 :

{-858993460, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
\___________________________________/ \/ not your 
       your array     \ array 

: ? (이 특별한 경우에) -858993460 때문에,

{9, 7, 2, 3, 5, 4, 1, 8, 6, 10, ?} 
\___________________________/ | 
      your array   +-- not your array 

과, 당신이와 끝까지 그런 다음 처음 10 개의 요소를 인쇄하면 출력 결과를 얻을 수 있습니다. 불행히도, 그 큰 음의 값을 보유하고 있던 변수 (또는 스택 제어 정보 또는 무엇이든)가 이제는 값 10으로 덮어 쓰여졌습니다. 실제로는 원하는 것이 아닙니다.

당신이하고있는 일은 정의되지 않은 동작입니다. 즉시 그만 해요.

merge_sort (a, 0, asize); 

로 :

merge_sort (a, 0, asize - 1); 

Answer 2

에 대한 이유를 찾기 위해 좀 도와주세요 얻을 배열의 끝 부분을 쓰레기통에 넣습니다. last은 asize-1이어야합니다 (즉, merge_sort(a, 0, asize-1);).

Answer 3

merge_sort(a, 0, asize); 

당신은 0asize-1에 요소에서 asize-1 즉를 보내야합니다. 다음은 올바른 것입니다! 당신의 결과 배열이 하나 개 이상 값과 하나 개 누락 된 값을 가지고 있기 때문에

merge_sort(a, 0, asize-1);