Bubblesort implementation in C++

Question

The parameters list contain the array that is passed to and the size of the array respectively. Is there anywhere I could improve my code?

void bubbleSort(int a[], int s) {
    for (int i = 1; i < s; i++) {
        for (int j = 0; j < s - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

Answer 1

Performance of your implementation is \$\Theta(N^2)\$ in all cases. You can improve it by holding a boolean variable indicating whether the current pass over the array swapped at least once the neighbouring array components. If the boolean is false, the array is sorted and we can exit the sort:

void bubbleSort(int a[], int s) {
    for (int i = 1; i < s; i++) {
        bool swapped = false;

        for (int j = 0; j < s - i; j++) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }

        if (!swapped) {
            return;
        }
    }
}

The above alternative implementation runs in linear time on almost sorted arrays.

Also, as you can see above, #include <utility> offers you a swapping routine (std::swap); why not use it?

Hope that helps.

Answer 2

void bubbleSort(int a[], int s)

Using a plain field, together with a second variable to denote the size would be (somewhat) fine in C, but not in C++. If you wish to call it C++, please use suitable containers from the STL which already provide methods to reliably query the number of contained elements and alike.

Another remark regarding the function signature: be more verbose with the naming of the parameters. When looking at the actual function it's not hard to guess that a might have been short for array and s might have been short for size, but using longer variable names doesn't hurt at all. The short loop variable names i and j are acceptable. You might also want to add the const modifier to s to stop you from accidentally modifying it inside the function.

Lastly, if you wish to pass an array size as an explicit parameter, use the correct data type. Depending on the platform, int may not be large enough to fully index the largest array possible. Use std::size_t from <cstdlib>. This also goes for your two loop variables.

A simple way to avoid size_t is to use the containers from the STL and their iterator interface instead.

---

int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;

Swapping two variables is a common problem. One already solved by the function std::swap() from <algorithm>.