CODEWITHSUNDEEP
arraysalgorithmsorting
howtechstuffworks
howtechstuffworks

Reputation: 1926

Outer loop N value of bubble sort

I am just learning sorting (not for the first time). In bubble sort, we have the following as the code. 

int bubble_sort(int *arr, size_t n) {

    size_t i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    return 0;
}

As you could all see, the inner loop has n-1 times (in for loop), which is understandable (a[i],a[i-1] is both involved in one iteration), but the outer loop have i < n, but it also works for i < n-1. But most implementation in internet have n as the outer loop value. Doing the outer loop n-1 works fine for worst case 5 4 3 2 1. Just wondering, if there is any set of inputs that will not work for n-1 times of outer loop . If there are please post it and explain. Thanks.

Upvotes: 1

Views: 887

Answers (2)

amit
amit

Reputation: 178471

No, there is no such input.

The rational is in Bubble-sort's proof. Recall that when proving that in bubble sort's i'th (outer) iteration - the i last elements are in place and sorted.

Thus, after the n-1 iteration, the last n-1 elements are in place and sorted, leaving only the remaining first element - that can be only in its correct place, the first place in the array.

(So, using this approach we can prove that bubble sort needs n-1 outer iterations at most)

Also note: classic bubble sort needs only n-i iterations in the inner loop (because of the rational I mentioned above), and NOT n-1.

Upvotes: 1

Joost
Joost

Reputation: 4134

N-1 is fine as well. As you describe, the worst case requires N-1 swaps (as the last has to become the first and vise-versa). If you add a print of the i-variable to the inside of the if-statement, you'll see that it's never called in the last iteration. This means that the last iteration of the loop never results in any swapping.

An even more efficient implementation of Bubblesort does not use a for-loop as an outer loop, though. Have a look at the bit of code below. Can you see the execution difference?

int bubble_sort(int *arr, size_t n) {
    size_t i,j;
    int flag = 1;
    while (flag) {
        flag = 0;
        for(j=0;j<n-1;j++) {
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;
            }
        }
    }
    return 0;
}

By setting the flag only if actual swapping occured, you'll end up jumping out of the loop much sooner when you're in an average case.

Upvotes: 3

Related Questions