recursive bubble sort help

This is a discussion on recursive bubble sort help within the C Programming forums, part of the General Programming Boards category; i can't get my head round it so i need some help with my project which is sort an array ...

  1. #1
    Registered User
    Join Date
    May 2012
    Posts
    1

    recursive bubble sort help

    i can't get my head round it so i need some help with my project which is sort an array of 50 items then display the largest numbers in LED's.


    Code:
      int num[50];
    
        void setup()
        {               
          pinMode(10, OUTPUT);
          pinMode(9, OUTPUT);
          pinMode(8, OUTPUT);
          pinMode(7, OUTPUT);
          pinMode(6, OUTPUT);
          pinMode(5, OUTPUT);
          pinMode(4, OUTPUT);
          pinMode(3, OUTPUT);
          Serial.begin(9600);
        }
    
        void loop()
        {
          reset();
          numberGen();
          numberSort();
          numberDisplay();
          delay(3000);
        }
    
        void reset()
        {
          digitalWrite(10, LOW);
          digitalWrite(9, LOW);
          digitalWrite(8, LOW);
          digitalWrite(7, LOW);
          digitalWrite(6, LOW);
          digitalWrite(5, LOW);
          digitalWrite(4, LOW);
          digitalWrite(3, LOW);
        }
    
        void numberGen()
        {
          for( int i = 0 ; i < 50 ; i++ )
          {
            num[i] = random(256);
          }
        }
    
        void numberSort()
        {
          int sizeOfArray = sizeof(num)/sizeof(int);
          int expect = 1;
          if ( expect != 0 )
          {
           {
            expect = 0;
            for( int a = 0 ; a < sizeOfArray ; a++ )
            {
              for ( int b = 1 ; b < sizeOfArray ; b++ )
              {
                if( num[b-1] > num[b] )
                {
                  int temp = num[b-1];
                  num[b-1] = num[b];
                  num[b] = temp;
                  expect++;
                }
              }
            }
            numberSort();
          }
        }
        expect = 0;
            for( int i = 0 ; i < sizeOfArray ; i++ )
            {
              for ( int j = 1 ; j < sizeOfArray ; j++ )
              {
                if( num[j-1] > num[j] )
                {
                  int temp = num[j-1];
                  num[j-1] = num[j];
                  num[j] = temp;
                  expect++;
                }
              }
            }
            numberSort();
          }
    
    
        void numberDisplay()
        {   
           int i = 10;
           int a = num[50];
           Serial.println(num[50]);
           while ( a > 0 )
           {
             int num = a % 2;
             a = a / 2;
             if( num == 1 )
             {
               digitalWrite(i, HIGH);
             }else{
               digitalWrite(i, LOW);
             }
             i--;
           }
        }



    I know that code does not work as when it loops round count is reset to 1 so the condition will never be true thus meaning it will loop round forever and ever. and my binary conversion is wrong here is an example a friend told me of how mine goes and how it should go:

    Your binary conversion doesn't work though... this is your
    numberDisplay() code. Here's an example. If you step through it with
    the number as 13.

    ----------
    i = 12
    a = 13

    while a > 0
    num = 1
    a = 6

    turn pin 12 on

    i = 11
    num = 0
    a = 3

    turn pin 11 off

    i = 10
    num = 1
    a = 1

    turn pin 10 on

    i = 9
    num = 1
    a = 0

    turn pin 9 on

    Result: 000000000101
    ----------

    This is 5 in binary, not 13. Also, this only displays the number at
    position 50 in the array. You need to display every number in the
    array.

    also he said "Is the second part of numberSort left in by mistake? You close the
    function, and then have some more code after it... the loops with i
    and j are outside of the numberSort function."

    please could someone help me with what i'm trying to do been at it for days and still no luck.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,673
    If you have an array declared with a number:

    int num[50];

    Then 50 isn't actually within the bounds of the array. This is a major problem, because whatever is in the same memory location as num[50] is being displayed, not any number in the array. It can make things look wrong.

    Continuing to your friend's example:
    ----------
    i = 12
    a = 13

    while a > 0
    num = 1
    a = 6

    turn pin 12 on

    i = 11
    num = 0
    a = 3

    turn pin 11 off

    i = 10
    num = 1
    a = 1

    turn pin 10 on

    i = 9
    num = 1
    a = 0

    turn pin 9 on

    Result: 000000000101
    ----------
    This doesn't make any sense. According to your friend, stepping through the algorithm turns on three pins. It looks like to me that he forgot to turn on the nine pin not the computer. You need to follow my advice about num[50] first, and decide if there is still a problem.

    But he is right that your function for sorting has code on the outside of it. If you don't move it into the function it won't even compile.
    Last edited by whiteflags; 05-30-2012 at 02:05 PM.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    2,554
    Hint: You will likely have to pass the array and its size to the recursive bubble sort function.

    Things to consider with recursive functions
    1. What is the stopping condition(s)?
    2. How is the problem made smaller or the solution moved closer to being found with each call of the function?

    Tim S.
    Last edited by stahta01; 05-30-2012 at 02:35 PM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Just to clarify, Are you required to implement a recursive bubble sort algorithm, or can you just write an iterative version? What is the actual requirement?

    What you have currently is two copies of the iterative sorting algorithm, although it will never reach the second one because you have infinite recursion around the first one (and the second).

    Why have you not used a loop within the setup and reset functions?
    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. Bubble sort help
    By BNoble in forum C Programming
    Replies: 20
    Last Post: 03-31-2011, 12:16 AM
  2. 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
  3. merge sort: recursive is fasfter than non-recursive
    By rio_cat in forum C Programming
    Replies: 8
    Last Post: 12-03-2006, 11:52 PM
  4. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 03:54 PM
  5. Bubble sort, Help!!!!
    By chema124 in forum C Programming
    Replies: 6
    Last Post: 01-21-2003, 03:02 PM

Tags for this Thread


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