동적 배열이 올바르게 초기화되지 않았습니다.

Question

두 개의 동적 배열을 사용하여 원래 배열을 정렬하는 프로그램을 작성했습니다. 하나는 왼쪽, 다른 하나는 오른쪽에 대한 정렬입니다.

그러나 동적 배열은 23 번째 줄과 28 번째 줄에서 원래 배열을받지 못합니다 (배열 전체에서 cout 메서드에 의해 입증 됨). 이들은 비어 있거나 범위를 벗어난 요소를 포함합니다. 따라서 프로그램이 전체적으로 작동하지 않습니다. 내 질문은 초기화 자체에 문제가 있습니까? 아니면 18-19 행의 선언과 함께 있습니까? 필자는 개인적으로 선언문과 함께 있다고 믿지만 동적 배열의 경우처럼 크기를 너무 많이 사용하고 싶지는 않습니다. 적절한 테스트를위한 모든 방법을 포함했지만, 불필요한 것으로 판단되는 경우이 질문을 편집합니다. 당신의 도움에 미리 감사드립니다.

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

void Merge(int *array, int left, int middle, int right) 
{ 
int * LArray; 
int * RArray; 
int counter = left;//This counter is used as a marker for the main array. 
int mid = middle; 

cout<<"Left " << left << "middle: "<< middle << " right: " << right<<endl; 

LArray = new int[middle-left + 1]; 
RArray = new int[right]; 

/*Initializes LArray*/ 
for (int i = left; i < middle - left + 1; i++) 
{ 
    LArray[i] = array[i]; 
} 

/*Initializes RArray*/ 
int temp = 0; 
for (int i = middle; i < right; i++) 
{ 
    RArray[temp] = array[i]; 
    temp++; 
} 

/*Prints out LArray*/ 
cout<<"LARRAY: "; 
for (int i = left; i < middle- left + 1; i++) 
{ 
    cout<<LArray[i]<< " "; 
} 

/*Prints out RArray*/ 
cout<<endl<<"RARRY: "; 
temp = 0; 
for (int i = middle; i < right; i++) 
{ 
    temp = 0; 
    cout<<RArray[temp]<< " "; 
    temp++; 
} 
cout<<endl; 

while (left <= middle && mid <= right) 
{ 
    /*This if statement checks if the number in the left array is smaller than the number in the right array*/ 
    if (LArray[left] < RArray[right]) 
    { 
     array[counter] = LArray[left]; 
     left++; 
     counter++; 
     cout<<"First if: array[counter]: "<< array[counter]<<" LArray[left]" << LArray[left]<<" left: "<< left<<" counter : "<< counter<<endl; 
    } 
    /*This else statement checks if the number in the right array is smaller than the number in the left array*/ 
    else 
    { 
     array[counter] = RArray[right]; 
     mid++; 
     counter++; 
     cout<<" First else: array[counter]: "<< array[counter] << " RArray[right] "<< RArray[right]<<" mid: "<< mid<<" counter : "<< counter<<endl; 
    } 
} 
/*If RArray is completed, check this one for any remaining elements.*/ 
while (left <= middle) 
{ 
    array[counter] = LArray[left]; 
    left++; 
    counter++; 
    cout<<" First while: array[counter]: "<< array[counter]<<" LArray[left]" << LArray[left]<<" left: "<< left<<" counter : "<< counter<<endl; 
} 

/*If LArray is completed, check this one for any remaining elements.*/ 
while (mid <= right) 
{ 
    array[counter] = RArray[right]; 
    mid++; 
    counter++; 
    cout<<" Second while: array[counter]: "<< array[counter] << " RArray[right] "<< RArray[right]<<" mid: "<< mid<<" counter : "<< counter<<endl; 
} 

delete [] LArray; 
delete [] RArray; 

} 


void MergeSort(int *array,int left, int right) 
{ 
if (left < right) 
{ 
    int middle = (left + right)/2; 
    MergeSort(array, left, middle); 
    MergeSort(array, middle + 1, right); 
    Merge(array, left, middle, right); 
} 
}; 

/*Checks if the array listed is sorted by looping through and checking if the current number is smaller than the previous.*/ 
bool IsSorted(int* array, unsigned long long size) 
{ 

for (int i = 0; i < size; i++) 
{ 
    cout<<array[i]<< " "; 
} 
cout<<endl; 
for (int i = 1; i < size; i++) 
{ 
    if (array[i] < array[i-1]) 
     return false; 
} 
return true; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
int array[8] = {5, 2, 4, 7, 1, 3, 2, 6}; 
MergeSort(array, 0, 8); 

bool check = IsSorted(array, 8); 

if (check) 
    cout<<"It is sorted!"; 
else 
    cout<<"It is not sorted!"; 
return 0; 
} 

Answer 1

병합 정렬의 개념은 배열을 두 개의 반쪽으로 재귀 적으로 분할하고 두 개의 반쪽을 정렬 한 다음 다시 병합하는 것입니다. 여기

내가 코드를 잘못 볼 수있는 것들 :

알고리즘과 문제가되지 않습니다

코드 불확실성 : 당신이 그것을 할당하고 있기 때문에

왼쪽 배열, 필요 이상으로 항상 큰 중간 요소를 가져 와서 초기화하십시오.

오른쪽 배열을 두 번 초기화합니다. 알고리즘과

실제 문제 : 당신은 제대로 카운터를 초기화하지 않을

, 그것은 항상 '0'으로 설정되고, 그래서 상관없이 호출 스택에 얼마나 깊이, 당신은 항상 설정되지 않은 요소 0 중간을 통해 왼쪽과 오른쪽 사이의 범위 대신 정렬 된 배열이됩니다.

당신은 권리가 그것을 할당하기 때문에 항상 옳다 배열의 요소의 수보다 큰 것 인수 바로 ... (가) 오른쪽 배열에 인덱스에 노력하고 - 중간 요소를.

또한 MergeSort 기능에 오류가 있습니다. 당신은 결코 실제로 [우측]이 RArray에 추가되지 않습니다 병합 기능 배열 이후 중간 요소를 정렬되지 않은, 그래서 첫 번째 재귀 호출을 정렬 할 것입니다, 당신은 중간 + 1에 전달하는 두 번째 재귀 호출에을 입력하면 정렬되지 않습니다.