Like Tree3Likes
  • 1 Post By std10093
  • 1 Post By iMalc
  • 1 Post By Adak

Bubble sort

This is a discussion on Bubble sort within the C Programming forums, part of the General Programming Boards category; Hello. I have a doubt about this code Code: #include <stdio.h> void bubble_sort(int []); #define LEN 5 int main( void ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    296

    Bubble sort

    Hello. I have a doubt about this code

    Code:
    #include <stdio.h>
    void bubble_sort(int []);
    #define LEN 5
     
    int main( void )
    {
        
            int array[LEN] = { 5 , 1 , 4 , 2 , 8 } , count =0  ;
            
            printf(" Before sorting ");
            
            for(; count<LEN; count++)
            printf(" %d " , array[count]);
            
            bubble_sort(array);
            
            printf(" After sorting ");
            
            count = 0;
            
            while( count < LEN )
            {
            printf(" %d " , array[count]);
            count++;
        }
     
            return 0;
    }
    void bubble_sort(int array[])
    {
            int i , j;
            
            for( i = LEN - 1; i >= 1; i-- )  // <-------
            {
                    printf("\n");
                    
                    for(j=0; j<5; j++)   // <-------
                    {
                            if( array[j] > array[j+1] )
                            
                            {
                                    int temp = array[j];
                                    array[j] = array[j+1];
                                    array[j+1] = temp;
                            }
                            
                            printf("\n %d" , array[j]);  // <----- print in every passing  
                    }
            }
            
            return;
    }
     
    /*
     
     Before sorting  5  1  4  2  8 
     
    1st passing  ( 4 >= 1)
     
     1
     4
     2
     5
     8
     
    2nd passing  ( 3 >= 1)
     
     1
     2
     4
     5
     8
     
    3rd passing  ( 2 >= 1)
     
     1
     2
     4
     5
     8
     
    4th passing ( 1 >= 1)
    
     1
     2
     4
     5
     8  
     
     After sorting  1  2  4  5  8 
     
     */
    I think the i>=1 it does one more passing that is unnecessary because the array is already sorted (after 3rd passing ).... I think i > 1 is the right. What is your opinion about that ? I had an argue with a friend about this.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    What would you sau for i>0 ?

    example
    Mr.Lnx likes this.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Location
    Douala, Cameroon
    Posts
    194
    well i ran your code and it printed 2 5s at the end of the sorting looking at the algorithm i think the mixup comes when j goes up to 4 and i comes down to 1 and there is the case when i and j are equal causing a problem.. let me edit and run..

  4. #4
    Registered User
    Join Date
    Nov 2011
    Location
    Douala, Cameroon
    Posts
    194
    check this out .. i tried this and the code sorts perfectly...

    Code:
    int i , j;
    
            for( i = LEN - 1; i >= 1 && i != j; i--)
            {
                printf("\n");
                for(j=0; j != i && j < LEN; j++)
                {
                    if( array[j] > array[j+1] )
                    {
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }

  5. #5
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    the array is already sorted
    I won't pretend to have gotten enough sleep last night to settle this myself, but don't forget that as far as a sorting algorithm knows, the array might already be sorted before it even starts. Just because the array you happen to be testing with IS sorted at that point, it doesn't mean your algorithm can assume that yet.

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    23
    This is a better solution, in this way if there aren't swaps(so it means that is ordered) it stops.
    Said formally, in the best case the time complexity of this implementation in 0(n) instead of O(n^2) of the classic one.
    Code:
    void bsort (int* array, int length){
    int i,j,flag=1,temp;
    
      for(i=0; (i<length-1) && flag; i++) {
            flag=0; 
    
            for (j=length-1; j>i; j--){
    
                   if( array[j-1] > array[j] ){
                          flag=1;
                          temp = array[j];
                          array[j] = array[j-1];
                          array[j-1] = temp;
                    }
             }
        }
    }
    Last edited by root; 11-16-2012 at 01:23 PM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Your original post has a buffer overrun. j<5 should be j<LEN-1.

    The easiest way to see if you have the boundary conditions correct is to see what happens if there are exactly two items. There should be only one compare, and if they were out of order then one swap.
    If you include the change I just mentioned above, then the original code will do exactly that. However, your i>1 idea would instead mean that zero comparisons are made and it would fail to sort.
    Therefore the outer loop is correct as-is; your friend was right, and you were wrong. But you both fail on missing the buffer overrun.
    Mr.Lnx likes this.
    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"

  8. #8
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    296
    Quote Originally Posted by iMalc View Post
    Your original post has a buffer overrun. j<5 should be j<LEN-1.

    The easiest way to see if you have the boundary conditions correct is to see what happens if there are exactly two items. There should be only one compare, and if they were out of order then one swap.
    If you include the change I just mentioned above, then the original code will do exactly that. However, your i>1 idea would instead mean that zero comparisons are made and it would fail to sort.
    Therefore the outer loop is correct as-is; your friend was right, and you were wrong. But you both fail on missing the buffer overrun.
    I face problems in understanding the algorithm. Not problems in C syntax or something about the language.

    I want to discuss with someone about it... I don't want to take some algorithm from web in order to give it in some exercise. Thank you for your time....

    On the topic now.... if we have 10 elements 0....9 for example... we really need 8 comparisons (inner loop) among the elements. (This technique is not the improvement of the algorithm of course).

    Generally if we have n elements we really need n-1 comparisons among the elements...... so inner loop would be concerned about that.

    Now... I can't understand how will be the outer loop . I think the number of outer passings is something different from comparisons into inner loop.

    for example PASSING 1 -> n-1 comparisons...
    PASSING 2-> n-1 comparisons... and so forth

    how can know the number of passings before go inner loop ? I just really confused... I can't understand... I have understood quicksort algorithm and now I face problems? :/
    Last edited by Mr.Lnx; 11-17-2012 at 03:23 AM.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    That's the problem with Bubble sort. It moves just one value, one index over, every time it iterates through the inner loop. It's fast on sorting small sets, but Insertion sort is faster. Once you start adding in the optimizations to Bubble sort to make it competitive with Insertion sort, you need more code - so you've gained nothing. It's still slower than Insertion sort, it's more code, and it's not as easy to remember.

    If you miss out on understanding Bubble sort's "secrets", imo, you haven't missed much.
    Mr.Lnx likes this.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Mr.Lnx View Post
    On the topic now.... if we have 10 elements 0....9 for example... we really need 8 comparisons (inner loop) among the elements. (This technique is not the improvement of the algorithm of course).
    Actually, the first pass would need 9 item comparisons in the inner loop.
    Code:
    0   1   2   3   4   5   6   7   8   9 // Item index
     \ / \ / \ / \ / \ / \ / \ / \ / \ /
      1   2   3   4   5   6   7   8   9   // 1st, 2nd 3rd comparisons etc
    Thre are modifications to bubble sort such that subsequent passes can be significantly shorter in some cases, or the algorithm may even terminate after any given pass if the sorting is detected as complete. But in all cases, the first pass contains N-1 comparisons.

    Think about how many comparisons are needed to determine if N items are in order. Because bubble sort can be made to exit after the first pass, no matter what, it still needs to do that much work in the first pass.
    Psst, check out my homepage, link below
    Last edited by iMalc; 11-17-2012 at 11:39 AM.
    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. using bubble sort to sort a matrix by sum..
    By transgalactic2 in forum C Programming
    Replies: 22
    Last Post: 12-22-2008, 11:03 PM
  2. bubble sort
    By nevrax in forum C Programming
    Replies: 1
    Last Post: 05-18-2007, 10:51 AM
  3. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 03:54 PM
  4. a little help with bubble sort
    By cman in forum C Programming
    Replies: 3
    Last Post: 02-06-2003, 02:45 AM
  5. My Bubble Sort, help
    By bluebob in forum C Programming
    Replies: 1
    Last Post: 04-02-2002, 02:52 AM

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