Thread: Bubble sort program stumped

As implemented, I do not think that is bubble sort. It may be a (slow) variant of selection sort. The element at index i is chosen, and then the elements after it in the array is compared with it. If the current element in the unsorted portion of the array is greater than the element at index i, they are swapped. Effectively, one finds the smallest element in the unsorted portion of the array and swaps it with the current element, but unlike normal selection sort there may be several unnecessary exchanges in between.

On the other hand, the basis for bubble sort is: compare adjacent elements. If they are not in order, swap them.

Well if you adopt a more rigorous approach to using braces, and correct indentation, it becomes plainly obvious that the loop which prints out the sorted array only happens ONCE when the whole array is sorted.

Code:

int main(void)
{
    int a[8];
    int i, j;

    for (i = 0; i < 8; ++i)
        if (scanf("&#37;d", &a[i])) {
            printf("Unordered data:  %d\n", a[i]);
        }
    for (i = 0; i < 8; ++i)
        for (j = i + 1; j < 8; j++)
            if (a[i] > a[j])
                swap(&a[i], &a[j]);
    for (i = 0; i < 8; ++i)
        printf("after pass 1:  %d\n", a[i]);
    getchar();
}

Then you should print \n only once

Code:

printf("Unordered data:");
for (i = 0; i < 8; ++i)
{
   if (scanf("&#37;d", &a[i]) == 1) 
   {
         printf(" %d", a[i]);
   }
}
printf("\n"); /* to finish a line */

The outer loop goes BACKWARDS from NUMBER - 1 to 0. The inner loop goes FORWARDS from 0 to j - 1. And the comparison always compares the ADJACENT elements a[i] and a[i + 1].

To be honest, I think the direction of the outer loop does not matter, and most examples I have seen replace it with a while loop controlled by a swap flag anyway. The direction of the inner loop only matters depending on whether you want to bubble small elements down or large elements up.

The first step is add braces to the code, in all the optional places where you left them out.

So

Code:

    for (i = 0; i < 8; ++i) {
        for (j = i + 1; j < 8; j++) {
            if (a[i] > a[j]) {
                swap(&a[i], &a[j]);
            }
        }
    }
    for (i = 0; i < 8; ++i) {
        printf("after pass 1:  &#37;d\n", a[i]);
    }

Second, if you want to print out something for each pass, then move the printing stuff inside the outer loop, but after the inner loop, say

Code:

    for (i = 0; i < 8; ++i) {
        for (j = i + 1; j < 8; j++) {
            if (a[i] > a[j]) {
                swap(&a[i], &a[j]);
            }
        }
        for (k = 0; k < 8; ++k) {
            printf("after pass %d:  %d\n", i, a[k]);
        }
    }

By always using braces, it makes it much easier to move code around, and be sure that it is going to still have the same effect that you expect.

You can then refine that to print the "after pass" only once, and all the numbers on the same line, say

Code:

    for (i = 0; i < 8; ++i) {
        for (j = i + 1; j < 8; j++) {
            if (a[i] > a[j]) {
                swap(&a[i], &a[j]);
            }
        }
        printf( "after pass %d:", i );
        for (k = 0; k < 8; ++k) {
            printf(" %d", a[k]);
        }
        printf( "\n" );
    }

Originally Posted by laserlight

To be honest, I think the direction of the outer loop does not matter, and most examples I have seen replace it with a while loop controlled by a swap flag anyway. The direction of the inner loop only matters depending on whether you want to bubble small elements down or large elements up.

Indeed, the direction of the loops is irrelevant, though some would call a one variant sink sort instead of bubble sort, but it is essentially the same thing.
I call the algorithm he used "simple sort" (and I'm not the only one).

btw, you can do even better than using a boolean 'swapped' flag. instead of setting a flag to true, you set an int to the position of the swap and... Oh I'll just show you:

Code:

void BestBubbleSort(int a[], int n) {
	int i = n-1;
	do {
		int k = 0;
		for (int j = 0; j < i; ++j) {
			if (a[j + 1] < a[j]) {
				Swap(a[j], a[j + 1]);
				k = j;
			}
		}
		i = k;
	} while (i > 0);
}

There you have your optimal bubble sort, which is kind of an oxymoron I suppose.

@iMalc, It's swap() not Swap()

swap() also takes the address, not value.

Originally Posted by zacs7

@iMalc, It's swap() not Swap()

swap() also takes the address, not value.

Ah well I copied and pasted from my own [C++] code and I use Swap which is diffferent.
Feel free to change it or:

Code:

#define Swap(a, b) swap(&a, &b)