Bubble sort program stumped

This is killing me
if i have 3 6 9 2 5 8 1 4


i have this sorter

Code:

for(i = 0; i < NUMBER; ++i)
     for (j = i + 1; j < NUMBER; ++j)
         if (a[i] > a[j])
           swap (&a[i], &a[j]);

with 8 random number intered it is supposed to output


Numbers entered: 3 6 9 2 5 8 1 4
next pass: 1 3 6 9 2 5 8 4
so on: .......
this is my code and it still doesnt do what I want it to do. Arrays and pointers are my week point can some one please help I am desperate

Code:

#include<stdio.h>

void swap(int*, int *);

int main(void)
{
        int a[8];
        int i,j;
        
        for(i = 0; i < 8; ++i)
          if(scanf("%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();
}

void swap(int *p, int *q) 
{
   int tmp;

   tmp =*p;
   *p = *q;
   *q = tmp;
}

If you want to print the content of the array after each pass, you need to add a block around the instructions. And of course, you can't use "i" in the outer loop and in the inner loop !

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(j = 0; j < 8; ++j)
  {
    printf("after pass 1:  &#37;d\n",a[j]);
  }
  getchar();
}

Indentation saves the day, woohoo !

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();
}

Yes
when i input 2 3 4 5 6 9 8 7
the output is
unordered data: 2
unordered data: 3
unordered data: 4
unordered data: 5
unordered data: 6
unordered data: 9
unordered data: 8
unordered data: 7
after pass1: 2
after pass1: 3
after pass1: 4
after pass1: 5
after pass1: 6
after pass1: 7
after pass1: 8
after pass1: 9

and it needs to be in this format

Numbers entered: 2 3 4 5 6 9 8 7
next pass: 2 3 4 5 6 7 8 9
so on: .......
with each pass moving the smallest number forward but only one at a time


and it needs to be in this format

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 */

Originally Posted by matthughes

Code:

for(i = 0; i < NUMBER; ++i)
     for (j = i + 1; j < NUMBER; ++j)
         if (a[i] > a[j])
           swap (&a[i], &a[j]);

This isn't even close to being a bubble sort. Your outer loop runs forwards instead of backwards, the inner loop doesn't start (or end) at the right place, and the inner loop comparison is not comparing the right quantities.

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].

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.

Ok it is a transportation element I still am boggled as to how to make the ouput look like
Numbers entered: 2 3 4 5 6 9 8 7
next pass:

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)