时间戳

首页 > 解决方案 > merge sort algorithm: std::out_of_range

c++ - merge sort algorithm: std::out_of_range

问题描述

I am currently making a merge sort algorithm but when i run the code i get an error says "terminate called after throwing an instance of 'std::out_of_range". This is my code.

template<typename T>
void merge(std::vector<T> &vec, int l, int m, int r){
    int i = l;
    int j = m + 1;
    int k = l;
    
    //CREATE TEMPORARY MEMORY
    int temp[vec.size()];

    while(vec.at(i) <= m && j <= r){
        if(vec.at(i) <= vec.at(j)){
            temp[k] = vec.at(i);
            i++;
            k++;
        }else{
            temp[k] = vec.at(j);
            j++;
            k++;
        }
    }
    while (i <= m){ //first half: Copy the remaining elements of first half, if there are any
        temp[k] = vec.at(i);
        i++;
        k++;
    }
    while (j <= r){ //second half: Copy the remaining elements of second half, if there are any 
        temp[k] = vec.at(j);
        j++;
        k++;
    }
    for(size_t p = 1; p <= r; p++){ //copy temp array to original array
        vec.at(p) = temp[k];
    }
}

Merge Sort Function

template<typename T>
void mergeSort(std::vector<T> &vec, int l, int r){
    if(l < r){ 
        int m = (l + r) / 2; //find midpoint
        mergeSort(vec, l, m); //first half
        mergeSort(vec, m + 1, r); //second half
        merge(vec, l, m, r); // merge
    }
}

标签： c++algorithmmergesortdsa

解决方案

您的函数中存在一些问题merge（您可以通过调试轻松发现）：

  1. vec.at(i) <= m将值与索引进行比较。这两个是无关的。所以改变：

    while(vec.at(i) <= m && j <= r){

    和：

    while(i <= m && j <= r){

  2. 最后一个循环开始于p = 1它是一个在许多情况下超出被合并范围的索引。所以改变：

    for(size_t p = 1; p <= r; p++){

    和：

    for(size_t p = l; p <= r; p++){

  3. 同一循环的主体k用作索引，但该变量与循环无关，并且具有超出考虑范围的值。所以改变：

    vec.at(p) = temp[k];

    和：

    vec.at(p) = temp[p];

通过这些更改，您的代码将起作用。

然而，遗憾的是temp始终具有完整向量的大小，而您只使用了它的一小部分。考虑减少内存使用。

推荐阅读