Thread: Can someone explain how this bubble sorting works?

  1. #1
    Registered User
    Join Date
    Oct 2017
    Posts
    39

    Can someone explain how this bubble sorting works?

    I get lost with all the loops, I understand it minimally, but I found this bubble sort algorithm online and experimented with numbers and ultimately got it to sort 100 random integers on the interval [1,20] in ascending order.

    Could someone help me with comments? I want to make sure I break the code down to the point I understand it fully for the next time I do it. This time is kind of different because we were never taught this. I understand the first for statement.

    Also, is there a way to remove duplicate numbers from the print statement that's printing in ascending order?

    Thanks.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    #include <string.h>
    
    
    int main() 
    {
    
    
    int i;
    int myArray[100];
    int j;
    int randNum;
    int a;
    srand(int()time(NULL));
    
    
    for (i = 0; i < 100; i++) // Will go through as long as i < 100, i=i+1 every iteration starting at 0.
    {
        randNum = rand() %20+1; // Gets 100 random integers on the interval [1,20]
        myArray[i] = randNum; // Assigning each of the generated random ints to the array myArray[i]
    }
    
    
    for (i=0; i<100; i++) 
    {
        for (j=0; j<100+1; j++)
        {
            if(myArray[j] > myArray[j+1])
            {
                a = myArray[j];
                myArray[j] = myArray[j+1];
                myArray[j+1] = a;
    
    
            }
        }
    }
    
    
    for(i=0; i<100; i++)
    {
        printf("Element: %d\n", myArray[i]);
    
    
    }
    return 0;
    }

  2. #2
    Banned
    Join Date
    Aug 2017
    Posts
    861
    run this
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    #include <string.h>
     
     // use smaller numbers to see what is going on
    int main() 
    {
     
     
    int i;
    int array[3] = { };
    int j;
    int randNum, num = 3, size;
    int temp;
    srand((int)time(0)); // Seeds Random Numbers
     
     size = sizeof(array)/sizeof(array[0]);
     
     printf("size = %d\n", size);
    for (i = 0; i < num ; i++) // Will go through as long as i < 100, i=i+1 every iteration starting at 0.
    {
        randNum = rand() %15; // Gets 100 random integers on the interval [1,20]
        array[i] = randNum; // Assigning each of the generated random ints to the array myArray[i]
    }
     
      for (i = 0; i < ( num - 1 ); i++) {
          for (j = 0; j < num - i - 1; j++) {
            printf("array[j]%d > array[j+1]%d\n",array[j] , array[j+1] );
            //if first number greater than second number hold it else where.
            if (array[j] > array[j+1]) 
            {
                //here
                temp = array[j];
               // move the smaller one where the bigger one was.
               array[j] = array[j+1];
               printf(" array[j] %d = array[j+1] %d\n",  array[j] , array[j+1]);
               
               array[j+1] = temp;
               //  put the greater one where the smaller one was
               // keep moving next time around the same two will no longer 
               // evalute to 3 > 1, but will be 1 > 3 = no move to the next one. 
            }
          }
        }
     
     
    for(i=0; i<num ; i++)
    {
        printf("Element: %d\n", array[i]);
     }
     
    return 0;
    }
    oh yes, remember
    Code:
    int j = 3;
    array[j] <--- j sets the element number not value inside of it;
    // so array[ j + 1] == what?
    if j = 3 , then it is looking into element number 2 : 0,1,2,3,4
    so j + 1 then is looking into element number 3 : 0,1,2,3,4
    which is one ahead of j.
    Code:
    array [2] = 3;
    array[3] = 1;
               3    >       1
    if ( array[j] > array [ j + 1])
    // you have to hold that value in a temp so it does not get lost when you over write its place setter/keeper.
      3   =    3
    temp = array[j];
    now move the lesser 1 to the "left"
    
                     < -- 1
    array[j] = array[j+1];
    
    then put the greater 3 in the lesser place.
    
                    < ---3
    
    array[j+1] = temp;
    
    ending up with
    array[j]=1 or array [ 2 ] = 1
    array[j+1] = 3 or array [ 3 ] = 3
    or
    1,3
    Last edited by userxbw; 10-16-2017 at 04:03 PM.

  3. #3
    Registered User
    Join Date
    Oct 2017
    Posts
    39
    Thank you! I believe I understand how it works now! The temporary variable holds the higher value. The lower value is then stored into array[j] and after it's moved down in the element, the higher value is now stored in array[j+1], hence the process of moving it up in the 100 elements. Eventually, it will get to t = 100 and then they'll be in ascending order.

    in the code,
    Code:
    for(j=0; j<100+1; j++)
    What does
    Code:
     j<100+1
    mean?

  4. #4
    Banned
    Join Date
    Aug 2017
    Posts
    861
    Quote Originally Posted by csmith03 View Post
    Thank you! I believe I understand how it works now! The temporary variable holds the higher value. The lower value is then stored into array[j] and after it's moved down in the element, the higher value is now stored in array[j+1], hence the process of moving it up in the 100 elements. Eventually, it will get to t = 100 and then they'll be in ascending order.

    in the code,
    Code:
    for(j=0; j<100+1; j++)
    What does
    Code:
     j<100+1
    mean?

    yes because it keep swapping them out lesser takes the greater's place, the greater moves ahead where the lesser was.

    bonus lession. to swap the order from , 1,2,3,4,5,6 to 6,5,4,3,2,1
    Code:
    switch it from this
      if (array[j] > array[j+1]) 
    
    // to this
    
      if (array[j] < array[j+1])
    What does
    Code:
     j<100+1
    mean?
    J < 101
    Last edited by userxbw; 10-16-2017 at 04:27 PM.

  5. #5
    Banned
    Join Date
    Aug 2017
    Posts
    861
    it is
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    #include <string.h>
     
     // use smaller numbers to see what is going on
    int main() 
    {
     
     
    int i, num = 10;
    
    int j;
    int randNum, size;
    int temp;
    srand((int)time(0)); // Seeds Random Numbers
     int array[num]; 
     size = sizeof(array)/sizeof(array[0]);
     
     printf("size = %d\n", size);
    for (i = 0; i < num ; i++) // Will go through as long as i < 100, i=i+1 every iteration starting at 0.
    {
        randNum = rand() %15; // Gets 100 random integers on the interval [1,20]
        array[i] = randNum; // Assigning each of the generated random ints to the array myArray[i]
    }
     printf("num = %d\n", num);
      for (i = 0; i < ( num - 1 ); i++)
      {
          printf(" i %d : num - 1 %d\n", i, (num-1) , i);
          
          for (j = 0; j < num - i - 1; j++) 
          {
              printf(" j %d num - i - 1 %d\n", j, ( num-i-1) );
           
            if (array[j] > array[j+1]) 
            {
                 
                temp = array[j];
               
               array[j] = array[j+1];
              
               
               array[j+1] = temp;
             
            }
          }
        }
     
     
    for(i=0; i<num ; i++)
    {
        printf("Element: %d\n", array[i]);
     }
     
    return 0;
    }
    Last edited by userxbw; 10-16-2017 at 04:28 PM.

  6. #6
    Registered User
    Join Date
    Oct 2017
    Posts
    39
    Interesting... Can I just put 101 instead of 100+1 then?

    Also, is there a way to add an if statement at the end and remove duplicating numbers in the print statement?

  7. #7
    Banned
    Join Date
    Aug 2017
    Posts
    861
    Quote Originally Posted by csmith03 View Post
    Interesting... Can I just put 101 instead of 100+1 then?
    what is that being used for?

    Also, is there a way to add an if statement at the end and remove duplicating numbers in the print statement?
    yes. I do not see why you can't you can pretty much put an if statement anywhere within a code block, and
    experimentation is a good thing to practice with coding. try it and see.
    Last edited by userxbw; 10-16-2017 at 04:41 PM.

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,608
    Hopefully this doesn't seem standoffish of an answer, but I recommend reading the bubble sort wikipedia page if you really want to understand it. The wikipedia page has some excellent animation and language to help you understand how it works the way it does. Perhaps watching swaps and such things will make it click.

    The basic rule that bubble sort follows is if two neighboring elements are out of order, you swap them. If you do this enough times, you will see the smaller elements percolate to the front of your array, which is why it is called bubble sort. The loops are largely there to make sure that enough swaps happen.

    This is exactly why bubble sort is something that maybe you commit to memory and then forget about. It is not a very smart sort; it doesn't take advantage of partially sorted arrays for instance, and it is only okay in small array sizes. Plus, in many real world scenarios, data is either mostly sorted or completely sorted already -- these considerations are important -- and yet bubble sort always works the exact same way. When you consider that something just as simple, like insertion sort does take advantage of partially sorted arrays, and scales well to larger sizes, bubble sort isn't great.

  9. #9
    SnoopFrogg KingFlippyNips's Avatar
    Join Date
    Sep 2016
    Posts
    33
    The University of San Fransico has really helpful sorting animations when it comes to sorting algorithms. Here's a link to the website: Comparison Sorting Visualization

    Hope that helps a bit.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Could you explain me #define works?
    By digioleg54 in forum C Programming
    Replies: 12
    Last Post: 05-17-2017, 01:18 PM
  2. Replies: 7
    Last Post: 09-14-2016, 07:56 PM
  3. Replies: 5
    Last Post: 02-27-2014, 08:09 AM
  4. Pls explain how this program works...
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 01-05-2002, 09:53 AM
  5. Can someone explain how this function works?
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 12-26-2001, 01:09 PM

Tags for this Thread