下記のマージソートのプログラムを作ったのですが、うまく動かない例が出てしまいました。
入力例
この入力だとデバッグした時にmergeのRもしくはLで読み取りアクセス違反を起こしてしまいます。
入力する個数が少ないときは上手くいくのですが、多いときに上手くいきません。
詳しい方いらっしゃったら解決方法を教えていただけると助かります。
cpp
1#include<iostream> 2#include<limits> 3#define INFINITY 0xFFFFFF 4void mergeSort(int* A, int left, int right); 5using namespace std; 6int ct = 0; 7int main() { 8 int* S; 9 int n; 10 cin >> n; 11 S = new int[n]; 12 for (int i = 0; i < n; ++i) { 13 cin >> S[i]; 14 } 15 /*for (int i = 0; i < n; ++i) { 16 cout << S[i]; 17 cout << " "; 18 } 19 cout << endl; 20 */ 21 mergeSort(S, 0, n); 22 23 for (int i = 0; i < n - 1; ++i) { 24 cout << S[i]; 25 cout << " "; 26 } 27 cout << S[n - 1] << endl; 28 cout << ct << endl; 29 30 return 0; 31 32} 33 34void merge(int* A, int left, int mid, int right) { 35 int n1 = mid - left; 36 int n2 = right - mid; 37 int* L; 38 int* R; 39 L = new int[n1 + 1]; 40 R = new int[n2 + 1]; 41 for (int i = 0; i < n1; ++i) { 42 L[i] = A[left + i]; 43 } 44 for (int i = 0; i < n2; ++i) { 45 R[i] = A[mid + i]; 46 } 47 L[n1] = (int)INFINITY; 48 R[n2] = (int)INFINITY; 49 int i = 0; 50 int j = 0; 51 52 for (int k = left; k < right; k++) { 53 if (L[i] <= R[j]) { 54 A[k] = L[i]; 55 i = i + 1; 56 ct++; 57 } 58 else { 59 A[k] = R[j]; 60 j = j + 1; 61 ct++; 62 } 63 } 64 delete[]L; 65 delete[]R; 66} 67 68void mergeSort(int* A, int left, int right) { 69 if (left + 1 < right) { 70 int mid = (left + right) / 2; 71 mergeSort(A, left, mid); 72 mergeSort(A, mid, right); 73 merge(A, left, mid, right); 74 } 75}
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。