4
\$\begingroup\$

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;
            }
        }
    }
}
\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oh, thanks. I never thought of that. One question is how come you use Θ to represent the runtime of the program, but not the big O, which represent the worst case of the program? In fact, I am not sure when to use Θ. \$\endgroup\$ – Herman Tam Sep 24 '16 at 8:05
  • 1
    \$\begingroup\$ @Herman: because big-O does not represent the worst case of the program, it represents an upper bound that may or may not be tight. If coderodde had said, "your implementation is O(N^2) in all cases" then that would mean, "your implementation is no worse than proportional to N^2 in all cases". The same would be true of an implementation that (impossibly) executes in constant time. Whereas the important part of what coderodde actually did say is, "in all cases your implementation is no better than proportional to N^2": Θ is an upper and a lower bound together. \$\endgroup\$ – Steve Jessop Sep 24 '16 at 8:11
  • \$\begingroup\$ @HermanTam You can think of it as follows: \$\mathcal{O}\$ is like \$\leq\$, \$\Theta\$ is like \$=\$. \$\endgroup\$ – coderodde Sep 24 '16 at 8:26
  • \$\begingroup\$ You're optimizing for one case; this does nothing when compared averaged on the N! possible orders of the elements. Maybe that is appropriate, but that's a big maybe. \$\endgroup\$ – Paul Draper Sep 24 '16 at 18:57
  • \$\begingroup\$ Oh, I see. But why is it N^2 when the sorting size gets smaller and smaller each step? \$\endgroup\$ – Herman Tam Oct 11 '16 at 5:00
3
\$\begingroup\$
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>.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.