Ошибка сегментации при реализации функции сортировки

Question

Я пытаюсь реализовать алгоритм сортировки, основанный на psuedocode, предоставленном для моего класса программирования, и я, и мой партнер постоянно получаем (сбрасываю ядро) ошибки, обычно именно Segmentation Fault. Я понимаю, что обычно это означает, что программа пытается получить доступ к памяти, к которой у нее нет доступа, но я не уверена, как решить проблему.

#include <iostream>
#include <cmath>

using namespace std;

void FlipFlopSort(int *Array, int begin, int end){
    int length = (end-begin);
    float midh = 2*(float)length/3;
    midh = ceil(midh);
    float midl = (float)length/3;
    midl = ceil(midl);
    //cout << "size of sorted area = " << length << endl;
    if(length<=2){
        //cout << "Length = 2" << endl;
        if(Array[begin] > Array[begin+1]){
            swap(Array[begin], Array[begin+1]);
        }
    }else{
        //cout << "Recursion Begin 1" << endl;
        FlipFlopSort(Array, begin, midh);
        //cout << "Recursion End" << endl;
        FlipFlopSort(Array, midl, end);
        //cout << "Recursion Begin 2" << endl;
        FlipFlopSort(Array, begin, midh);
    }
}

int main(){
    // Declare Variables and Read Inputs
    int n;
    cin >> n;

    int Array[n];

    for(int i = 0; i < n; i++){
        cin >> Array[i];
    }

    FlipFlopSort(Array, 0, n);


    for(int i = 0; i<n; i++){
         if(i != (n-1)){
             cout << Array[i] << " ";
         }else{
             cout << Array[i] << endl;
         }
    }

    return 0;

}

Answer 1

Начнем с:

    int n;
    cin >> n;

    int Array[n];

1. Почему подписанный тип? Размеры массивов не могут быть объявлены как подписанные типы.
2. C ++ строго запрещает объявление массива переменного размера в стеке (т.е. так, как вы это сделали). Это также устаревшая функция C. Вместо этого вы должны написать:

    int* Array = new int[n];

Одна из причин, по которой вы можете получить ошибку сегментации, заключается в следующей строке:

    if (length <= 2) {
        //cout << "Length = 2" << endl;
        if (Array[begin] > Array[begin + 1]) {
            swap(Array[begin], Array[begin + 1]);
        }
    }

1. Если длина равна меньше или равно 2, означает ли это, что оно имеет как минимум 2 элемента? Может иметь 0 или 1. Вы должны добавить проверку в начале вашей функции:

void FlipFlopSort(int *Array, int begin, int end){
    int length = (end-begin);
    if (length <= 1) {
        return;
    }
    ...
}

Другая причина в том, что вы вычисляете средние размеры , а не индексы означает, что вы не добавляете начало к ним.

рассмотрите: начало = 100, конец = 103. -> длина = 3, midl = 1 и midh = 2. Имеет смысл? нет! Это недопустимые показатели в этом контексте. Вы должны были написать

midh += begin;
midl += begin;

после их вычисления.

Последнее, вы должны избегать использования чисел с плавающей запятой (если вам НЕ ДЕЙСТВИТЕЛЬНО это нужно), поэтому я бы написал:

    const int midl = begin + length / 3;
    const int midh = begin + 2 * midl;

Это не эквивалентно тому, что вы написали, но оно все еще работает, хотя ваши - рискованные (максимальные значения слишком сомнительны, потому что вы можете оказаться в конце массива).

void FlipFlopSort(int* Array, int begin, int end) {
    const int length = end - begin;
    if (length <= 1) {
        return;
    }

    const int midh = begin + 2 * length / 3;
    const int midl = begin + length / 3;

    //cout << "size of sorted area = " << length << endl;
    if (length <= 2) {
        //cout << "Length = 2" << endl;
        if (Array[begin] > Array[begin + 1]) {
            swap(Array[begin], Array[begin + 1]);
        }
    }
    else {
        FlipFlopSort(Array, begin, midh);
        FlipFlopSort(Array, midl, end);
        FlipFlopSort(Array, begin, midh);
    }
}

Answer 2

Вы должны убедиться, что length равно как минимум 2, когда вы swap, иначе вы будете менять номера за пределами. Ваши значения midl и midh в настоящее время неверны. Они относятся к begin, поэтому вам нужно добавить к ним begin. Однако вы можете добавить midl к самому Array и пропустить параметр begin в своей функции, чтобы упростить интерфейс.

Я бы также заменил операции с плавающей запятой std::ceil на целочисленную версию .

// A function to do integer division and return the ceil value
size_t DivCeil(size_t dividend, size_t divisor) {
    return 1U + ((dividend - 1U) / divisor);
}

void FlipFlopSort(int* Array, size_t length) {
    if(length > 2) {
        // calculate midl & midh
        size_t midl = DivCeil(length, 3U);
        size_t midh = DivCeil(2U * length, 3U);

        FlipFlopSort(Array, midh);
        // add midl to Array and sub midl from length
        FlipFlopSort(Array + midl, length - midl);
        FlipFlopSort(Array, midh);
    } else if(length == 2) {
        if(Array[1] < Array[0]) {
            // swap the values
            std::swap(Array[0], Array[1]);
        }
    } // else length < 2 ... don't do anything
}

#include <iostream>
#include <vector>

int main() {
    size_t n;
    if(std::cin >> n) { // check that the user entered a number
        // don't use VLA:s, use a std::vector instead
        std::vector<int> Array(n);

        for(size_t i = 0; i < Array.size(); ++i) {
            std::cin >> Array[i];
        }

        FlipFlopSort(Array.data(), Array.size());

        for(int value : Array) {
            std::cout << value << '\n';
        }
    }
}

Если вы хотите, чтобы ваш алгоритм сортировки стал более универсальным c и использовался со стандартными контейнерами, вы можете заменить входные параметры итераторами.

Пример :

#include <algorithm> // std::iter_swap
#include <iterator>  // std::distance, std::next

// A function to do integer division and return the ceil value
template<typename T>
T DivCeil(T dividend, T divisor) {
    return 1 + ((dividend - 1) / divisor);
}

template<typename It>
void FlipFlopSort(It begin, It end) {
    auto length = std::distance(begin, end);     // iterator version of "length = end-begin"
    static constexpr decltype(length) two = 2;   // constant of the same type as length
    static constexpr decltype(length) three = 3; // -"-

    if(length > two) {
        // calculate midl & midh iterators
        auto midl = std::next(begin, DivCeil(length, three));
        auto midh = std::next(begin, DivCeil(two * length, three));

        FlipFlopSort(begin, midh);
        FlipFlopSort(midl, end);
        FlipFlopSort(begin, midh);
    } else if(length == two) {
        if(*std::next(begin) < *begin) {
            // swap the values pointed at by the iterators
            std::iter_swap(begin, std::next(begin));
        }
    } // else length == 1 or 0 ... don't do anything
}

Использование:

#include <iostream>
#include <vector>

int main() {
    size_t n;
    if(std::cin >> n) {
        std::vector<int> Array(n);

        for(size_t i = 0; i < Array.size(); ++i) {
            std::cin >> Array[i];
        }

        FlipFlopSort(std::begin(Array), std::end(Array));

        for(int value : Array) {
            std::cout << value << '\n';
        }
    }
}