View unanswered posts | View active topics It is currently Sat Dec 20, 2014 6:45 am






Reply to topic  [ 14 posts ] 
Bubble Sorting 
Author Message
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Bubble Sorting
Hey There,

I need a bubble sorting algorithm for RobotC for the following numbers: Rand0, Rand1, Rand2, Rand3, Rand4, Rand5, Rand6, Rand7.

If someone could do that that would be amazing.

Thanks!


Mon Jul 23, 2012 2:36 pm
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3297
Location: Rotterdam, The Netherlands
Post Re: Bubble Sorting
You're in luck, check out my tutorial :)
http://botbench.com/blog/2012/07/21/tut ... your-data/

It was published 2 days ago.

- Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Mon Jul 23, 2012 2:43 pm
Profile WWW
Site Admin
Site Admin

Joined: Thu May 24, 2012 12:15 pm
Posts: 619
Post Re: Bubble Sorting
Now, that's just good luck... :D

_________________
Check out our Blog! And our Facebook page!
Need help? Take a look at our Wiki and our Forums.

I just met you,
And this is crazy,
But here's my code now,
So fix it, maybe?
~ Carly Rae Jepsen parody


Mon Jul 23, 2012 3:49 pm
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
Slight optimization for the bubble sort:
Code:
while (true)
{
  int swapCount = 0;
  for(int j = 0; j < (MAX_NUMBERS - 1); j++)
  {
    if (arr[j] > arr[j+1])
    {
      temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
      swapCount++;
    }
  }
  if (swapCount == 0)
  {
    break;
  }
}


Mon Jul 23, 2012 4:37 pm
Profile
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Re: Bubble Sorting
Thanks Xander!
Could someone by any chance explain the code a little more detailed.
Code:
for(int i = 0; i < MAX_NUMBERS; i++)
{
  for(int j = 0; j < (MAX_NUMBERS - 1); j++)
  {
    if (arr[j] > arr[j+1])
    {
      temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

How would I implement my own numbers? I'm not too familiar yet with Arrays.


Tue Jul 24, 2012 11:08 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
According to your code, you could easily make it into an array.
Code:
#define MAX_NUMBERS    8
task main()
{
    int randNum[MAX_NUMBERS];

    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        randNum[i] = random[1000];
    }
    ....
}

As the name suggested, air is lighter than water. So a bubble at the bottom of a water column will rise slowly to the top. The algorithm is basically doing an N-pass to the number column. In each pass, it compares each element with its adjacent neighbor below. If its neighbor below is smaller (lighter weight), it switches position with the neighbor. So in effect, the neighbor below rises. So as each pass progresses, each lighter element that is out of place will rise one position up. So for an N-element column, the worst case is having the lightest element at the bottom of the column, so it takes N passes for the bottom element to rise to the top of the column which is its proper place.


Last edited by MHTS on Tue Jul 24, 2012 11:39 am, edited 2 times in total.



Tue Jul 24, 2012 11:19 am
Profile
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Re: Bubble Sorting
Okay, what about if I have a number1 and number2 and my max number is 8.

How would I implement that into this code?

Code:
for(int i = 0; i < MAX_NUMBERS; i++)
{
  for(int j = 0; j < (MAX_NUMBERS - 1); j++)
  {
    if (arr[j] > arr[j+1])
    {
      temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}


Tue Jul 24, 2012 11:23 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
Code:
#define MAX_NUMBERS    8
task main()
{
    int randNum[MAX_NUMBERS];
    //
    // Initialize the array with random numbers.
    //
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        randNum[i] = random[1000];
    }
    //
    // Now, sort them.
    //
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        for(int j = 0; j < (MAX_NUMBERS - 1); j++)
        {
            if (randNum[j] > randNum[j+1])
            {
                int temp;
                //
                // The random number at j is larger than its next neighbor j + 1.
                // So swap them.
                //
                temp = randNum[j];
                randNum[j] = randNum[j+1];
                randNum[j+1] = temp;
            }
        }
    }
}


Tue Jul 24, 2012 11:36 am
Profile
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Re: Bubble Sorting
The problem is, I don't know how to implement my data. :crying: Can someone explain to me how to implement it? I'm so confused.. haha.


Tue Jul 24, 2012 11:44 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
The above algorithm will do MAX_NUMBERS passes no matter what. Even in the best case when the array is already sorted (i.e. all the numbers are in ascending order already), it will still do MAX_NUMBERS passes without any swapping. Therefore, that's where the slight optimization comes in. It basically keeps track of how many swaps we did in each pass. If we did not swap anything in a pass, it is safe to assume that all numbers are in order so we quit.
Code:
#define MAX_NUMBERS    8
task main()
{
    int randNum[MAX_NUMBERS];
    //
    // Initialize the array with random numbers.
    //
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        randNum[i] = random[1000];
    }
    //
    // Now, sort them.
    //
    while (true)
    {
        int swapCount = 0;
        for(int j = 0; j < (MAX_NUMBERS - 1); j++)
        {
            if (randNum[j] > randNum[j+1])
            {
                int temp;
                //
                // The random number at j is larger than its next neighbor j + 1.
                // So swap them.
                //
                temp = randNum[j];
                randNum[j] = randNum[j+1];
                randNum[j+1] = temp;
                swapCount++;
            }
        }

        if (swapCount == 0)
        {
            break;
        }
    }
}


Tue Jul 24, 2012 11:49 am
Profile
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Re: Bubble Sorting
Alright, since I'm still pretty confused I will show you what I have already. (Trying to make a program play some tones and then after they have played them they play them again but this time in the correct [smallest to largest] order.)

Code:
task main()
{
    int rand0 = 1046;
    int rand1 = 659;
    int rand2 = 523;
    int rand3 = 784;
    int rand4 = 698;
    int rand5 = 988;
    int rand6 = 587;
    int rand7 = 880;

    PlayTone(rand0,10);
    nxtDisplayTextLine(0,"Tone: %d", rand0);
    wait1Msec(1000);
    PlayTone(rand1,10);
    nxtDisplayTextLine(1,"Tone: %d", rand1);
    wait1Msec(1000);
    PlayTone(rand2,10);
    nxtDisplayTextLine(2,"Tone: %d", rand2);
    wait1Msec(1000);
    PlayTone(rand3,10);
    nxtDisplayTextLine(3,"Tone: %d", rand3);
    wait1Msec(1000);
    PlayTone(rand4,10);
    nxtDisplayTextLine(4,"Tone: %d", rand4);
    wait1Msec(1000);
    PlayTone(rand5,10);
    nxtDisplayTextLine(5,"Tone: %d", rand5);
    wait1Msec(1000);
    PlayTone(rand6,10);
    nxtDisplayTextLine(6,"Tone: %d", rand6);
    wait1Msec(1000);
    PlayTone(rand7,10);
    nxtDisplayTextLine(7,"Tone: %d", rand7);
    wait1Msec(5000);
   
#define MAX_NUMBERS    8
 int randNum[MAX_NUMBERS];
 
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        randNum[i] = random[1000];
    }

    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        for(int j = 0; j < (MAX_NUMBERS - 1); j++)
        {
            if (randNum[j] > randNum[j+1])
            {
                int temp;
                temp = randNum[j];
                randNum[j] = randNum[j+1];
                randNum[j+1] = temp;
            }
        }
    }
}

How would I get rand0 - rand7 implemented into this bubble algorithm?

Thanks so much!!!


Tue Jul 24, 2012 11:54 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
Simon1 wrote:
The problem is, I don't know how to implement my data. :crying: Can someone explain to me how to implement it? I'm so confused.. haha.

Now I am confused. Doesn't the above code implement what you had on the other post? On the other thread, you had the code to generate 8 random numbers to 8 variables. I changed the 8 variables into one array variable with 8 elements. Then I applied the bubble sorting algorithm to it. At the end, you will have an array with all the numbers in sorting order. The only thing left to do is to add the code to play the tone.
Code:
for (int i = 0; i < MAX_NUMBERS; i++)
{
    PlayTone(randNum[i],10);
    nxtDisplayTextLine(i,"Tone: %d", randNum[i]);
    wait1Msec(1000);
}


Tue Jul 24, 2012 11:56 am
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1368
Post Re: Bubble Sorting
Code:
#define MAX_NUMBERS    8
task main()
{
    int randNum[MAX_NUMBERS];
    //
    // Initialize the array with random numbers.
    //
    randNum[0] = 1046;
    randNum[1] = 659;
    randNum[2] = 523;
    randNum[3] = 784;
    randNum[4] = 698;
    randNum[5] = 988;
    randNum[6] = 587;
    randNum[7] = 880;
    //
    // Play the tone unsorted.
    //
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        PlayTone(randNum[i],10);
        nxtDisplayTextLine(i,"Tone: %d", randNum[i]);
        wait1Msec(1000);
    }
    //
    // Now, sort them.
    //
    while (true)
    {
        int swapCount = 0;
        for(int j = 0; j < (MAX_NUMBERS - 1); j++)
        {
            if (randNum[j] > randNum[j+1])
            {
                int temp;
                //
                // The random number at j is larger than its next neighbor j + 1.
                // So swap them.
                //
                temp = randNum[j];
                randNum[j] = randNum[j+1];
                randNum[j+1] = temp;
                swapCount++;
            }
        }

        if (swapCount == 0)
        {
            break;
        }
    }
    //
    // Play the tones sorted.
    //
    for (int i = 0; i < MAX_NUMBERS; i++)
    {
        PlayTone(randNum[i],10);
        nxtDisplayTextLine(i,"Tone: %d", randNum[i]);
        wait1Msec(1000);
    }
}


Tue Jul 24, 2012 12:03 pm
Profile
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
Post Re: Bubble Sorting
YES! That's how you do it! Thanks so much! You have been so helpful. The program works wonderfully, and I think I finally understand how it works.

Thanks again.


Tue Jul 24, 2012 1:28 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 14 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.