recursive bubble sort help

[Beardyman]

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: Select all

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.

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

[philba]

I have no idea why you are using recursion here.

First off, it's not a good idea on a micro with a limited stack. While recursion has some elegance, it's evil on micros. Secondly, you appear to have a complete bubble sort (order N^2) and then you recurse at the bottom of the outer loop. What's the point of that? And, I don't see how your recursion ever ends. when does it stop recursing?

By the way, you can speed up the sort by observing that at the end of the first pass of the inner loop, the largest number is at the end of the array.

If you simply MUST use recursion, why not sort the largest element to the end of the array and recurse on the subarray that is one smaller (exclude the cell at the end).

Plus, you have some junk code after the numbersort routine. not sure what the compiler does with it.

[floresta]

I have no idea why you are using recursion here.

It's because his teacher, the one who created the project assignment, doesn't have a clue about the difference between a computer and a controller.

Don

[philba]

I had thought about that but I can't imagine why a teacher doing microcontrollers would even bother with a bubble sort, let alone recursion.

[Beardyman]

i manged to do a bubble sort with a recrusice function

Code: Select all

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);
for( int a = 0 ; a < sizeOfArray-1 ; a++ )
{
if( num[a+1] > num[a] )
{
int temp = num[a+1];
num[a+1] = num[a];
num[a] = temp;
}
}
}




void numberDisplay()
{
int i;
for(i=7; i>=0; i--)
{
if ((num[0] & (1 << i)) == 0)
{
digitalWrite(i+3, LOW);
}
else
{
digitalWrite(i+3, HIGH);
}
}
}

could someone change this into a bubble sort for me please my heads about to explode

[floresta]

I had thought about that but I can't imagine why a teacher doing microcontrollers would even bother with a bubble sort, let alone recursion.

It's because the teacher most likely has a programming background rather than an engineering background.

As far as the administrators are concerned:
-Computer science teachers have a lot of programming experience.
-A microcontroller requires programming.
-Therefore computer science teachers are qualified to teach microcontroller programming courses.

As we all know programming courses typically include bubble sorts, inverting matrices etc, etc. That's what the teacher learned in school and that's what (s)he now uses when teaching 'programming'.

Don

[philba]

could someone change this into a bubble sort for me please my heads about to explode

Grasshopper, it is time to spread your wings.

[adafruit_support_mike]

Looking at the code, I think you've been modifying it long enough that it's reached the 'big ball of mud' stage.. the point where trying to read what's there is harder than starting over from scratch.

Among other things, I can see an unnecessary set of braces in numberSort() (lines 50 & 68), plus a short-circuited conditional:

Code: Select all

  int expect = 1;
  if ( expect != 0 )


which doesn't serve any purpose.

Now, back in the elder days I was a regular on PerlMonks, where one of the rules is "don't ask us to do your homework for you," so without giving you the exact code, let me walk you through some basic ideas of the bubble sort.

First of all, I agree with everyone else that bubblesort isn't an algorithm that lends itself well to recursion. It's best done with a couple of nested loops. Having said that though, it's always possible to convert loops into recusive code and vice versa.

When you use recursion, there's one important rule: always, always, ALWAYS pass an argument. The argument is what tells you when to stop:

Code: Select all

void recur (int depth) {
    if( 0 == depth ) {
        return;         //  stop the recursion
    }
    //  do something that involves the current value of depth

    recur( depth - 1 );
}


From there, the trick is to break your algorithm down into jobs that can be done based on the argument you pass.

To discuss the bubblesort, let's make some assumptions: we have an array of items with indices 0..N ; we want the end result of the sort to put the smallest item at index 0 and the largest at index N ; and we want to start each pass through the array at index 0.

You can change any or all of those, but those constraints let me discuss the algorithm without having a bazillion, "do this (or that (assuming condition X) or the other (assuming condition Y))" disclaimers.

So.. to bubblesort, we start with the item at 0 and compare it to the item at 1. If the item at 1 is larger, we swap the items, and if not we do nothing. Then we compare items 1 and 2, 2 and 3, etc, swapping along the way. By the time we get to N-1 and N, we can assume that the largest item has 'bubbled' its way up to index N. We can't assume squat about the rest of the array though, so we have to make another pass to get the second-largest item in index N-1. Repeat for N-2, N-3, N-4, etc.

By this point, you should see a pattern that fits into the model of recursion I showed above.

[Beardyman]

thanks for you're help but i manged to do it this morning after i got some sleep got an A for all my programmes so thanks for your help

[floresta]

I rest my case.

Don