Segmentation Fault in the implementation of a sorting function

Question

I am trying to implement a sorting algorithm based on psuedocode provided for my programming class and me and my partner have been consistently getting (core dumped) errors, usually Segmentation Fault specifically. I understand that usually means the program is trying to access memory it is not allowed to, but I'm unsure how to fix the issue.

#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

Let's start with:

    int n;
    cin >> n;

    int Array[n];

1. Why is n a signed type? arrays sizes can't be declared as signed types.
2. C++ strictly forbids declaring variable sized array on the stack (i.e. the way you did). It is also a deprecated feature of C. You should write instead:

    int* Array = new int[n];

One of the reasons you might be getting a segmentation fault is because of the following line:

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

1. If length is less-than or equal to 2, does it mean it has at least 2 elements? It might have 0 or 1. You should add a check in the beginning of your function:

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

Another reason, is because you compute the middle sizes and not indices, meaning, you don't add begin to them.

consider: begin=100, end=103. -> length = 3, midl = 1 and midh = 2. Makes sense? no! These are not valid indices in this context. You should have written

midh += begin;
midl += begin;

after their computation.

Last thing, you should avoid using floating points (unless you REALLY need to) so I would write:

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

It is not equivalent to what you wrote, but it still works, while your's is risky (ceiling values is fishy beacause you might find yourself over the end of the array).

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

You must make sure that length is at least 2 when you swap, or else you'll be swapping numbers out of bounds. Your midl and midh values are currently wrong. They are relative to begin, so you need to add begin to them. You could however add midl to the Array itself and skip the begin parameter in your function to simplify the interface.

I'd also replace the floating point std::ceil operations with an integer version.

// 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';
        }
    }
}

If you want your sorting algorithm to be made more generic and usable with the standard containers, you could replace the input parameters with iterators.

Example:

#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
}

Usage:

#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';
        }
    }
}