Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
            }
        }
    }
}
share|improve this question

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.

share|improve this answer
    
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 Θ. – Herman Tam yesterday
1  
@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. – Steve Jessop yesterday
    
@HermanTam You can think of it as follows: \$\mathcal{O}\$ is like \$\leq\$, \$\Theta\$ is like \$=\$. – coderodde yesterday
    
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. – Paul Draper yesterday
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>.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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