Bubble sort with modification (offset)

Question

My task is to write bubble sort modification, in which the number of comparisons is reduced by about half.

I already wrote my standard bubble sort algorithm:

void bubble_sort(int* tab, int roz)
{
    int test;
    for (int i = 0; i < roz; i++)
    {
        for (int j = 1; j < roz; j++)
        {
            if (tab[j - 1] > tab[j])
            {
                test = tab[j - 1];
                tab[j - 1] = tab[j];
                tab[j] = test;
            }
        }
    }
}

And how to modify it to co complete the task? How the code will look like?

Answer 1

Well you can optimize your solution using the following:

On first iteration of the algorithm you know for sure that the last element is the greatest. So it is already in order. No need to loop till the end of the array in your inner loop.

On each new iteration one more element is in order. So you can reduce the next inner loop count by 1.

I took the liberty to modify a bit your solution.

int lastUnsorted = n - 1;
bool isSorted = false;

while (!isSorted)
{
    isSorted = true;
    for (int i = 0; i < lastUnsorted; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            isSorted = false;
            int temp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = temp;
        }
    }
    lastUnsorted--;
}