Where could be the problem in the bubble sort code?

Question

I have problem, the code sorts well "tab", returns the correct result, but "tab2", already returns the wrong result (7 6 4 0 4 1 3 1 5 6 6 7 8 9 9). Unfortunately, I don't see any error in the code, everything seems correct to me

#include <iostream>

void sort(int* begin, int* end) {
    for (int* i = begin; i != end; ++i) {
        //std::cout << *i<< std::endl;

        for (int* j = i+1 ; j < end ; ++j) {
            //std::cout << *(j - 1)<<" " << *j << std::endl;
            if (*(j - 1) > *j) {
                std::swap(*(j - 1), *j);
            }
        }
    }
}

void write(int* begin, int size)
{
    while (size > 0)
    {
        std::cout << *begin << ' ';
        ++begin;
        --size;
    }
}

int main()
{
    int tab[10] = { 0, 9, 1, 3, 8, 2, 6, 7, 5, 4 };
    sort(tab, tab + 10);
    write(tab, 10);

    std::cout << '\n';

    int tab2[16] = { 9, 7, 8, 6, 5, 4, 4, 0, 9, 6, 7, 1, 6, 3, 1, -100 };
    sort(tab2, tab2 + 15);
    write(tab2, 15);
}

Answer 1

You have two loops and only use the inner loop's index in comparison and swap. The classic bubble sort uses both indexes. The element at the outer index gets the largest value that comes after it.

So the fix is:

            if (*i > *j) {
                std::swap(*i, *j);
            }

Alternatively, the issue might be that the inner loop's start moves forward before the lowest value reaches the bottom. You can clearly see it if you print the list after each iteration. In this case, the fix would be starting the inner loop not at the outer loop's cursor, but after the first element.

    for (int* i = begin; i <= end; ++i) {
        for (int* j = begin+1 ; j <= end ; ++j) {
            if (*(j - 1) > *j) {
                std::swap(*(j - 1), *j);