Bubble sort program stumped

This is a discussion on Bubble sort program stumped within the C Programming forums, part of the General Programming Boards category; This is killing me if i have 3 6 9 2 5 8 1 4 i have this sorter Code: ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    27

    Question 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;
    }

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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 !

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,443
    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();
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    27
    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

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    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 first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by matthughes View Post
    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].

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    May 2007
    Posts
    27
    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:

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,443
    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" );
        }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    Quote Originally Posted by laserlight View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    @iMalc, It's swap() not Swap()

    swap() also takes the address, not value.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    Quote Originally Posted by zacs7 View Post
    @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)
    Last edited by iMalc; 05-17-2007 at 01:30 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program Plan
    By Programmer_P in forum C++ Programming
    Replies: 0
    Last Post: 05-11-2009, 01:42 AM
  2. bubble sort
    By nynicue in forum C Programming
    Replies: 7
    Last Post: 04-15-2009, 05:09 AM
  3. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  4. bubble sort not working with struct...
    By Jenica in forum C++ Programming
    Replies: 1
    Last Post: 10-12-2004, 12:54 PM
  5. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21