Recursive Bubble Sort

Question

I am having some trouble with this. We basically have been asked to create two versions of a program that will sort an array of 50 items then display the largest numbers in LED's. I have got it working using a basic bubble sort and it displaying. My issue is when I have to do this using recursion. Unfortunately my knowledge on recursion is very limited as I missed the lecture on it -.- He has also not put the notes online. I have had a long google however still can't get my head around it. So I ask a few things. Firstly, could someone explain recursion in relation to a bubble sort using sedo code. Secondly, am I completely wrong with my attempt.

int numbers[49];

void setup()
{                
  pinMode(12, OUTPUT);
  pinMode(11, OUTPUT);
  pinMode(10, OUTPUT);
  pinMode(9, OUTPUT);
  pinMode(8, OUTPUT);
  pinMode(7, OUTPUT);
  pinMode(6, OUTPUT);
  pinMode(5, OUTPUT);
  Serial.begin(9600);
}

void loop()
{
  resetLEDLow();
  genNumbers();
  sortNumbers();
  displayNumber();
  delay(5000);
}

void resetLEDLow()
{
  digitalWrite(12, LOW);
  digitalWrite(11, LOW);
  digitalWrite(10, LOW);
  digitalWrite(9, LOW);
  digitalWrite(8, LOW);
  digitalWrite(7, LOW);
  digitalWrite(6, LOW);
  digitalWrite(5, LOW);
}

void genNumbers()
{
  for( int i = 0 ; i < 50 ; i++ )
  {
    numbers[i] = random(256);
  }
}

void sortNumbers()
{
  int sizeOfArray = sizeof(numbers)/sizeof(int);
  int check = 1;
  if( check != 0 )
  {
    check = 0;
    for( int i = 0 ; i < sizeOfArray ; i++ )
    {
      for ( int j = 1 ; j < sizeOfArray ; j++ )
      {
        if( numbers[j-1] > numbers[j] )
        {
          int temp = numbers[j-1];
          numbers[j-1] = numbers[j];
          numbers[j] = temp;
          check++;
        }
      }
    }
    sortNumbers();
  }
}

void displayNumber()
{   
   int i = 12;
   int a = numbers[49];
   Serial.println(numbers[49]);
   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. So, what do I need to change or is what I am doing not really recursion at all?

Really need some help with this, got my brain going round and around.

Edit: Here is my attempt with the new recursion. I have removed code not relevant to the problem.

void loop()
{
  int topLevel = 0;
  int currentSort = 0;
  int sizeOfArray = sizeof(numbers)/sizeof(int);
  int numbers[49];
  sortNumbers(topLevel,currentSort,sizeOfArray,numbers);
}

int sortNumbers(p,c,l,numbers)
{
 // Swap if they are in the wrong order
 if( numbers[c-1] > numbers[c] )
 {
   int temp = numbers[c-1];
   numbers[c-1] = numbers[c];
   numbers[c] = temp;
 }
 // If we have finished this level and need to go to next level
 if( c == l )
 {
   c = 0;
   p++;
 }
 // Finished
 if( p == l+1 )
 {
   return numbers;
 }
 // Continue to the next place
 return sortNumbers(p,c+1,l, numbers);
}

Sort50Rec:-1: error: 'p' was not declared in this scope Sort50Rec:-1: error: 'c' was not declared in this scope Sort50Rec:-1: error: 'l' was not declared in this scope Sort50Rec:-1: error: 'numbers' was not declared in this scope Sort50Rec:-1: error: initializer expression list treated as compound expression Sort50Rec.cpp: In function 'void loop()': Sort50Rec:19: error: 'numbers' was not declared in this scope Sort50Rec:21: error: 'sortNumbers' cannot be used as a function Sort50Rec.cpp: In function 'void genNumbers()': Sort50Rec:42: error: 'numbers' was not declared in this scope Sort50Rec.cpp: At global scope: Sort50Rec:46: error: redefinition of 'int sortNumbers' Sort50Rec:-1: error: 'int sortNumbers' previously defined here Sort50Rec:46: error: 'p' was not declared in this scope Sort50Rec:46: error: 'c' was not declared in this scope Sort50Rec:46: error: 'l' was not declared in this scope Sort50Rec:46: error: 'numbers' was not declared in this scope

I am sure part of it is the way I am naming my function and am I right in thinking you can only return one value? Or not?

Edit: Fixed error pointed out new error.

    void loop()
{
  int topLevel = 0;
  int currentSort = 0;
  int numbers [49];
  int sizeOfArray = sizeof(numbers)/sizeof(int);
  numbers = sortNumbers(topLevel,currentSort,sizeOfArray,numbers);
}

int sortNumbers(int p,int c,int l,int numbers)
{
 // Swap if they are in the wrong order
 if( numbers[c-1] > numbers[c] )
 {
   int temp = numbers[c-1];
   numbers[c-1] = numbers[c];
   numbers[c] = temp;
 }
 // If we have finished this level and need to go to next level
 if( c == l )
 {
   c = 0;
   p++;
 }
 // Finished
 if( p == l+1 )
 {
   return numbers;
 }
 // Continue to the next place
 return sortNumbers(p,c+1,l, numbers);
}

Sort50Rec.cpp: In function 'void loop()': Sort50Rec:19: error: invalid conversion from 'int*' to 'int' Sort50Rec:19: error: initializing argument 4 of 'int sortNumbers(int, int, int, int)' Sort50Rec:19: error: incompatible types in assignment of 'int' to 'int [49]' Sort50Rec.cpp: In function 'void genNumbers()': Sort50Rec:40: error: 'numbers' was not declared in this scope Sort50Rec.cpp: In function 'int sortNumbers(int, int, int, int)': Sort50Rec:47: error: invalid types 'int[int]' for array subscript Sort50Rec:47: error: invalid types 'int[int]' for array subscript Sort50Rec:49: error: invalid types 'int[int]' for array subscript Sort50Rec:50: error: invalid types 'int[int]' for array subscript Sort50Rec:50: error: invalid types 'int[int]' for array subscript Sort50Rec:51: error: invalid types 'int[int]' for array subscript Sort50Rec.cpp: In function 'void displayNumber()': Sort50Rec:71: error: 'numbers' was not declared in this scope

Thanks

possible duplicate of Understanding Recursion (applying it on Bubble Sort) — Oliver Charlesworth
– Oliver Charlesworth, Commented May 21, 2012 at 14:25
@OliCharlesworth I've taken a look at that. However, I am still unsure as to how it works. You mind shedding some light? — Kyle93
– Kyle93, Commented May 21, 2012 at 14:45
You haven't said what types the variables (p,c,l,numbers) are in your function declaration int sortNumbers(p,c,l,numbers) — forsvarir
– forsvarir, Commented May 23, 2012 at 15:01
@forsvarir Whoops, thanks for pointing that out. Sorted that although I have an new issue will edit and work on it now — Kyle93
– Kyle93, Commented May 23, 2012 at 15:03

Kevin · Accepted Answer · 2012-05-23 15:55:04Z

2

You have a redundant check causing an infinite loop.

void sortNumbers()
{
  ...
  int check = 1;
  if( check != 0 )
  {
    ...
    sortNumbers();
  }
}

Now, since this is clearly homework, I'll just give some general advice. In general, you use recursion to make a problem of a particular size smaller. Figure out what part of the problem is getting smaller each iteration, and just make each iteration a recursive call instead of a loop (hint: this means you'll probably want to pass some value into the method to tell you the size and/or location of the current iteration). And remember to have a check either at the beginning of the method or before you recurse to check the size of the problem.

void loop()
{
  int topLevel = 0;
  int currentSort = 0;
  /* You never initialize this - what's supposed to be in it? */
  int numbers [49];
  int sizeOfArray = sizeof(numbers)/sizeof(int);
  /* Two things here: you're passing an array (numbers) in where the 
     sortNumbers() function has it declared as an int;
     and the return value is declared as an int, but you're storing it 
     into an array. */
  numbers = sortNumbers(topLevel,currentSort,sizeOfArray,numbers);
}

/* You're going to have to change this method signature - you're working 
   with arrays, not plain ints. You're changing numbers[] inline, so you 
   don't need to return anything. */
int sortNumbers(int p,int c,int l,int numbers)
{
 /* The first iteration has c = 0, so [c-1] is going to be out-of-bounds. 
    Also, when c = l, [c] will be out of bounds. */
 if( numbers[c-1] > numbers[c] )
 {
   int temp = numbers[c-1];
   numbers[c-1] = numbers[c];
   numbers[c] = temp;
 }
 if( c == l )
 {
   c = 0;
   p++;
 }
 if( p == l+1 )
 {
   return numbers;
 }
 return sortNumbers(p,c+1,l, numbers);
}

This isn't how I was thinking of doing it, but I believe it should work once you fix the problems I've pointed out (and possibly some I missed).

edited May 23, 2012 at 15:55

answered May 21, 2012 at 15:15

Kevin

56.6k15 gold badges107 silver badges139 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Kyle93 Over a year ago

Hi @Kevin Edit - . I think I know what you mean now. If I edit the main post with my go would you mind taking a look.

Kevin Over a year ago

@Kyle93 If it's working, post it on code review (make sure to phrase it so it fits with their faq, if there's a particular problem with it (e.g. segfault) post another question here. If it's just not quite right yet, add it here. Either way, post a link to it and I'll take a look.

Kyle93 Over a year ago

Cheers @Kevin It's not quite working yet. I am having issues with variables not being declared in scope. However arduino is not so helpful with errors. I will edit the post now to include my go and the error. Thanks

norbeen · Accepted Answer · 2019-09-25 13:48:58Z

0

def bubbleSort(myArray, lenArray):

    if lenArray==1:
        return myArray

    else:
        for i in range(len(myArray)-1):
            if (myArray[i]>myArray[i+1]):
                myArray[i], myArray[i+1] = myArray[i+1], myArray[i]
        return bubbleSort(myArray, lenArray-1)

myArray= [2,3,56,7]
lenArray= len(myArray)
print(bubbleSort(myArray, lenArray))

answered Sep 25, 2019 at 13:48

norbeen

311 bronze badge

1 Comment

Saeed Zhiany Over a year ago

Welcome to SO, it may your answer is correct, but always explain your answer by at least a few sentences.

Collectives™ on Stack Overflow

Recursive Bubble Sort

2 Answers 2

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related