Thread: bubble sort algorithm - displaying content

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    35

    bubble sort algorithm - displaying content

    Hello,

    I am working on a bubble sort program and it is kicking my butt. I have been learning C for about 6 weeks now 1-2 times a week when I have the time away from work and family.

    One of the items I am working on is a bubble sort program. I have listened to lecture after lecture, read and followed the tutorial (which did not work for me) on cprogramming.com and looked at multiple other examples.

    I am not good at understanding techinese yet. I need some help displaying this. I have two programs. I am working in linux.

    My first program generates psuedo random numbers. I pipe the generated numbers over to the find program which contains the bubblesort algorithm to look for a specfic number and display those numbers in order.

    The numbers I am trying to sort are (using a seed for the psuedo random numbers):
    17767
    9158
    39017
    18547
    56401
    23807
    37962
    22764
    7977
    31949
    22714
    55211
    16882

    Now, the command for this is:
    ./generate 13 1

    Now I use the pipe character to send those numbers to the find program as such ./generate 13 1 | ./find 9158

    The find program has the bubble sort algorithm. I think the algorithm is correct but I cannot get this to diplay correctly to save my life.

    Code:
    void
    sort(int values[], int n)
    {
        // O(n^2) sort
        for(int i=n-2;i>0;i--) {
            for(int j=0;j<i;j++) {
                if(values[j]>values[j+1]) {
                    int tempholder=values[j+1];
                    values[j+1]=values[j];
                    values[j]=tempholder;
                    printf("%d\n",values[j]);
                }
            }
        }
    return;
    }
    Now it should display
    7977
    9158
    16882
    17767
    18547
    22714
    22764
    23807
    31949
    37962
    39017
    55211
    56401

    Instead it displays:
    9158
    18547
    23807
    37962
    22764
    7977
    31949
    22714
    55211
    23807
    37962
    22764
    7977
    31949
    22714
    22764
    7977
    31949
    22714
    22764
    7977
    22714
    7977
    22714
    7977
    22714
    7977
    7977

    My two biggest issues:
    1. I don't quite understand what I am doing with the bubblesort even after everything that I have read. I understand it probably 70% of the way.
    2. I know that I have the printf() in the wrong place but I have tried it in numerous places to no avail so I figure maybe I have programmed something wrong.

    Any help would be greatly appreciated.

    Thank you,

    Wayne

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Print the array of numbers after they're sorted, not while you're sorting them. Take the printf right out of the sort routine. Print the array in the function that you call sort from, after you call it.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Apr 2012
    Posts
    35
    I have tried that already.
    Code:
    void
    sort(int values[], int n)
    {
        // TODO: implement an O(n^2) sort
        for(int i=n-2;i>0;i--) {
            for(int j=0;j<i;j++) {
                if(values[j]>values[j+1]) {
                    int tempholder=values[j+1];
                    values[j+1]=values[j];
                    values[j]=tempholder;
                }
            printf("%d\n",values[j]);
            }
        }
    return;
    }
    Output
    9158
    17767
    18547
    39017
    23807
    37962
    22764
    7977
    31949
    22714
    55211
    9158
    17767
    18547
    23807
    37962
    22764
    7977
    31949
    22714
    39017
    9158
    17767
    18547
    23807
    22764
    7977
    31949
    22714
    37962
    9158
    17767
    18547
    22764
    7977
    23807
    22714
    31949
    9158
    17767
    18547
    7977
    22764
    22714
    23807
    9158
    17767
    7977
    18547
    22714
    22764
    9158
    7977
    17767
    18547
    22714
    7977
    9158
    17767
    18547
    7977
    9158
    17767
    7977
    9158
    7977

    AND

    Code:
    void
    sort(int values[], int n)
    {
        // TODO: implement an O(n^2) sort
        for(int i=n-2;i>0;i--) {
            for(int j=0;j<i;j++) {
                if(values[j]>values[j+1]) {
                    int tempholder=values[j+1];
                    values[j+1]=values[j];
                    values[j]=tempholder;
                }
            }
        printf("%d\n",values[j]);
        }
    return;
    }
    ERROR
    make find
    gcc -ggdb -std=c99 -Wall -Werror -o find find.c helpers.c -lcs50 -lm
    helpers.c: In function 'sort':
    helpers.c:46:26: error: 'j' undeclared (first use in this function)
    helpers.c:46:26: note: each undeclared identifier is reported only once for each function it appears in
    make: *** [find] Error 1

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by scrfix View Post
    I have tried that already.
    No you didn't. Printing them after the array has been sorted means completely outside all the loops involved in sorting. Eg;

    Code:
    sort (values, n);  // your actual sort call in main or wherever
    
    for (i = 0; i < n; i++) printf("%d\n", values[i]);  // completely separate event
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You also don't need a return statement at the end of a void function.
    Returning is what a function just does when it has nowhere left to go.
    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"

  6. #6
    Registered User
    Join Date
    Apr 2012
    Posts
    35
    Thank you so much for input and helping with that. I finally got it to print out in descending order. I am going to work on getting it in ascending order. I could not do exactly what you suggested because the function being called was actually in another file that was not included in to the first. I kept getting an error stating that it didn't know about the variables which was true so I added like so below and it is now working.

    Code:
    void
    sort(int values[], int n)
    {
    int i,j,k;
        // TODO: implement an O(n^2) sort
        for(i=n-2;i>0;i--) {
            for(j=0;j<i;j++) {
                if(values[j]>values[j+1]) {
                    int tempholder=values[j+1];
                    values[j+1]=values[j];
                    values[j]=tempholder;
                }
            }
        }
    for(k=n-2;k>0;k--) {
      printf("%d\n",values[k]);
    }
    }

  7. #7
    Registered User
    Join Date
    Apr 2012
    Posts
    35
    I ran in to some issues sorting them realizing that I was missing some of the numbers that were being passed through and it wasn't sorting all of the numbers so I made a correction to the function. Now I don't know whether or not that is correct or not. All of the tutorials I read stated it was n-2 so that you didn't give a chance to outside the bounds of the array or get an unexpected bug in the function however I found that when doing n-2 I couldn't get all of the numbers sorted so I had to change it to n-1 and then correct the ascending and descending orders.

    Code:
    void
    sort(int values[], int n)
    {
    int i,j,k;
        // TODO: implement an O(n^2) sort
        for(i=n-1;i>0;i--) {
            for(j=0;j<i;j++) {
                if(values[j]>values[j+1]) {
                    int tempholder=values[j+1];
                    values[j+1]=values[j];
                    values[j]=tempholder;
                }
            }
        }
    for(k=n-1;k>=0;k--) {
      if(k==n-1)
        printf("\nDescending Order:\n");
      printf("%d\n",values[k]);
    }
    for(k=0;k<n;k++) {
      if(k==0)
        printf("\n\nAscending Order:\n");
      printf("%d\n",values[k]);
    }
    }

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    n-1 is the highest allowable index. Since j is always LESS than i, and i is maximum n-1, your j+1 index will stay in bounds. So it looks okay.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble sort algorithm
    By Mr.Lnx in forum C Programming
    Replies: 37
    Last Post: 09-16-2011, 03:48 PM
  2. Replies: 4
    Last Post: 02-10-2011, 02:50 PM
  3. testing a bubble sort algorithm
    By rushhour in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2009, 01:00 AM
  4. Help, bubble-sort algorithm
    By webznz in forum C Programming
    Replies: 6
    Last Post: 10-30-2007, 01:28 AM
  5. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM

Tags for this Thread