Comparing iterators crashes program without errors in custom bubble sort implementation

Question

I'm relatively new to C++. I have been trying to use iterators to sort a vector. I'm using bubble sort. I don't want to know if my bubble sort implementation works or not, I just want to know what's crashing my program.

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter &j = end; j != start; j--) {
        for (iter &i = start; i != end; i++) {
            // std::cout << *i << std::endl;
            if (*i > *(i + 1)) { // this line is where it stops
                std::iter_swap(i, i + 1);
            }
        }
    }

    std::cout << "ended"; // this line never gets called
}

When the program stops, though, it doesn't show any exceptions. I also try-catched the part where it stopped, but it didn't go in the try catch. Also, whenever I un-comment the first printing line:

std::cout << *i << std::endl;

It prints 1168169449 forever. What is going wrong here?

I'm testing it like this:

std::vector<int> vector = {1, 2, 3, 6, 4, 5};
std::vector<int> temp = vector;
//std::sort(temp.begin(), temp.end());
bubbleSort(vector.begin(), vector.end());
for(auto& num : vector) {
    std::cout << num << std::endl;
}

Are `i` and `j` supposed to be references? Why not just use `start` and `end` directly if they are? — Alan Birtles, Jun 02 '20 at 22:19
*Comparing Iterators Crashes Program Without Error* Crashing the program's a pretty big error. If you mean no compiler error, the compiler's tasked with translating your source code into binary code, and to do that it needs only to make sense grammatically. With a few exceptions that have been codified as grammatical rules because they always result in incorrect code, the compiler has no say in whether or not the program makes sense logically. It's the same in any language. Watch a political debate or advertisements to see grammatically correct logical nonsense by the shovel full. — user4581301, Jun 02 '20 at 22:26
What @AlanBirtles asked makes sense (but I have no more votes Today to show it) :-). I don't understand how this could work with only the change suggested in the answers. When the inner loop has executed once, `start == end`. Next time around, `start > end` since `end` has been decreased and then the inner loop is likely going to blow up the computer. — Ted Lyngmo, Jun 02 '20 at 22:33

anastaciu · Accepted Answer · 2020-06-04T11:54:43.973

In that line you are dereferencing i + 1, in the last iteration of the cycle it will dereference .end() which invokes undefined behavior, .end() is one past the last element, it can't be dereferenced.

Quick fix is to make your stop condition i != end - 1.

This, though will not fix the the bubble sort implementation which would still be flawed for more complex sequences, take this sample vector:

std::vector<int> vector = {1, 2, 7, 3, 6, 4, 5};

As you can see here, it will not be sorted correctly.

A possible correction would be:

Demo

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter i = start + 1; i != end; i++) {
        for (iter j = start; j != end - 1; j++) {
            if (*i < *j) {
                std::iter_swap(i, j);
            }
        }
    }
    std::cout << "ended" << std::endl;
}

This version, though it works as intended, could be optimized, you could do away with one of the copies at the cost of a slightly less readable code and optimize the number of iterations:

template<typename iter>
void bubbleSort(iter start, iter end) {
    while(start != end) {
        for (iter j = start; j != end; j++) {
            if (*start > *j) {
                std::iter_swap(start, j);
            }
        }
        start++;
    }
    std::cout << "ended" << std::endl;
}

Another thing you could do is to add a condition do to avoid dereferencing and comparing values in the same position, removing some overhead whith less indirection calls.

//...
if(start == j){ // will compare the iterators and skip the loop if they are equal
    continue;
}
//...

All things considered, I would use something like this:

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter i = start; i != end; i++) {
        for (iter j = i; j != end; j++) {
            if(i == j) {
                continue;
            }
            if (*i > *j) {
                std::iter_swap(i, j);
            }
        }
    }
    std::cout << "ended" << std::endl;
}

As said in the linked thread, performance is deppendant of several factors among which are the CPU architecture, the SO or the compiler, you must test these solutions and see which one gives you the best performance.

You can also use your compiler optimization options to adjust the compilation to your needs.

Derek C. · Answer 2 · 2020-06-02T23:19:02.563

You are dereferencing the end iterator which you cannot dereference.

In your loop you go through each iterator until the end. Problem is, you plus the iterator each time. When the iterator is equal to end - 1 and you add that one to it you will receive end which you then dereference. This is undefined behaviour, thus the random number.

You could try changing the loop condition to be != end - 1 which would mean i + 1 could never be end.

Comparing iterators crashes program without errors in custom bubble sort implementation

2 Answers2