マージソート - 範囲外のベクトルのサブスクリプト

Question

私は、ベクトルを使用して、すでに動作している基数ソートとともに、マージソートプログラムを取得しようとしています。

しかし、マージソートでは、常に "Vector subscript out of range"というエラーが表示されます。私はこのエラーがなぜ現れるのか知っていますが、私はそれを止めるために何を変えなければならないのか分かりません。

コード：

#include "Includes.h" 

class Mergesort 
{ 
public: 

std::vector<int> mergeSort(std::vector<int> list, int low, int high, int max) 
{ 
    int mid; 

    if (low < high) // Does not continue to merge sort when low is less than high. 
    { // This will be when the given set is a single number. 
     mid = low + (high - low)/2; 
     list = mergeSort(list, low, mid, max); // Split the given set into two halves down the middle. 
     list = mergeSort(list, mid + 1, high, max); 
     list = merge(list, low, mid, high, max); 
    } 

    return list; 
} 

std::vector<int> merge(std::vector<int> list, int low, int mid, int high, int max) // Call requires the bottom, middle and top numbers of the set. 
{ 
    int h, i, j, k; 
    std::vector<int> listb(max); // Merged list. 
    h = low - 1; 
    i = low - 1; 
    j = mid; 

    while ((h <= mid) && (j <= high)) 
    { 
     if (list[h] <= list[j]) // If the low part of the array is less than the upper middle of the array, 
     { 
      listb[i] = list[h]; // The next number in the merged array becomes h (initially low part). 
      h++; // Increment h to the next part of the array 
     } 
     else // Otherwise, 
     { 
      listb[i] = list[j]; // The next number in the merged array becomes j (initially upper middle). 
      j++; // Increment j to the next part of the array. 
     } 
     i++; // Always increment i, the position of the merged array. Starts at the bottom of the array. 
    } // End of while loop 

    if (h > mid) // If h - the progress from the bottom of the array - is beyond the middle. 
    { 
     for (k = j; k <= high; k++) // Loop until k is out of the array's range. 
     { 
      listb[i] = list[k]; // Set the next element in the merged array to the k element in the unmerged. 
      i++; // I.e. this starts from the middle, goes to the top of the array copying it into the merged one. 
     } 
    } 
    else // Otherwise, progress has not reached the the j value 
    { 
     for (k = h; k <= mid; k++) // K will start from h instead 
     { 
      listb[i] = list[k]; 
      i++; 
     } 
    } 
    // Then, 
    for (k = low; k <= high; k++) // Loop through the entire original array, copying the merged array into it. 
    { 
     list[k] = listb[k]; 
    } 

    return list; 
} 
}; 

メイン：

#include "Mergesort.h" 
#include "Radixsort.h" 

// Import things we need from the standard library 
using std::chrono::duration_cast; 
using std::chrono::milliseconds; 
using std::cout; 
using std::endl; 
using std::this_thread::sleep_for; 

// Define the alias "the_clock" for the clock type we're going to use. 
// (You can change this to make the code below use a different clock.) 
typedef std::chrono::steady_clock the_clock; 

using namespace std; 

Mergesort mergeSorter; 
Radixsort radixSorter; 

void main() 
{ 
int num, i = 0, j = 0, k = 0; 
int inputNumber = 0; 

cout << "Please input the size of the list to sort, then press enter:" << endl; 
cin >> num; 

vector<int> intList(num); 

cout << endl << "Please enter a 1 for manual input or 2 for random generation between 0 and 99, then press enter:" << endl; 
while (j != 1 && j != 2) 
{ 
    cin >> j; 
    if (j != 1 && j != 2) 
    { 
     cout << "Please enter 1 or 2." << endl; 
    } 
    else 
    { 
     cout << endl; 
    } 
} 
if (j == 1) 
{ 
    cout << "Now, Please enter the " << num << " numbers, pressing enter between each:" << endl; 
    for (i = 0; i < num; i++) 
    { 
     cin >> inputNumber; 
     intList[i] = (inputNumber); 
    } 
} 
else if (j == 2) 
{ 
    for (i = 0; i < num; i++) 
    { 
     inputNumber = rand() % 100; 
     intList[i] = (inputNumber); 
    } 
    cout << "The list generated is: "; 
    for (std::vector<int>::iterator it = intList.begin(); it != intList.end(); it++) // Loops through the list, printing it out. 
    { 
     cout << *it << " "; 
    } 
    cout << endl << endl; 
} 

cout << endl << "Now, Please enter a 1 for merge sort or 2 for radix sort, then press enter:" << endl; 
while (k != 1 && k != 2) 
    { 
     cin >> k; 
     if (k != 1 && k != 2) 
     { 
      cout << "Please enter 1 or 2." << endl; 
     } 
    } 

if (k == 1) 
{ 
    intList = mergeSorter.mergeSort(intList, 1, num, num); 
    cout << endl << "So, the sorted list using merge sort will be:"; 
} 
else if (k == 2) 
{ 
    intList = radixSorter.radixSort(intList, num); 
    cout << endl << "So, the sorted list using radix sort will be:"; 
} 
cout << endl << endl; 

for (std::vector<int>::iterator it = intList.begin(); it != intList.end(); it++) // Loops through the list, printing it out. 
{ 
    cout << *it << " "; 
} 
cout << endl << endl; 
} 

Answer 1

パラメータmaxが使用されることはありません。通常、mergesortの正しいインデックスは終了インデックス（ベクトルの最後のインデックスより1つ多い）です。 merge（）では、hとiをlow-1に設定すると、範囲外の問題が発生し、lowとlow-1の両方に設定されます。マージソートの主コードがあるべき

void mergeSort(std::vector<int> &list, int low, int high) 

void merge(std::vector<int> &list, int low, int mid, int high) 

：

if ((high-low) > 1) // nothing to do if 0 or 1 elements 
    { // This will be when the given set is a single number. 
     mid = low + (high - low)/2; 
     mergeSort(list, low, mid); 
     mergeSort(list, mid, high); 
     merge(list, low, mid, high; 

では、初期の行がなければならないマージバックリストにマージコピーので、次にマージとマージパラメータのための基準を用いてボイド関数でなければなりません：<を用いて他の線

h = low; 
    i = low; 
    j = mid; 

    while ((h < mid) && (j < high)) // change <= to < 

は= <を使用するように変更されなければなりません。

並べ替えをマージする最初の呼び出しは次のようになります。

mergeSort(std::vector<int> list, 0, list.size()); 

あなたは代わりにint型のインデックスのためのsize_t型を使用したい場合があります。