View unanswered posts | View active topics It is currently Sun Sep 20, 2020 6:45 pm

 Page 1 of 2 [ 16 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Bubble Sorting
Author Message
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
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

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3654
Location: Rotterdam, The Netherlands
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

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

_________________
Check out our Blog! And our Facebook page!
Need help? Take a look at our updated help documentation and the ROBOTC Forums.

Mon Jul 23, 2012 3:49 pm
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
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
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
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
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
Re: Bubble Sorting
According to your code, you could easily make it into an array.
 Code:#define MAX_NUMBERS    8task 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
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
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
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
Re: Bubble Sorting
 Code:#define MAX_NUMBERS    8task 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
Rookie

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

Tue Jul 24, 2012 11:44 am
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
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    8task 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
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
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
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
Re: Bubble Sorting
 Simon1 wrote:The problem is, I don't know how to implement my data. 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
Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1523
Re: Bubble Sorting
 Code:#define MAX_NUMBERS    8task 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
Rookie

Joined: Thu Jul 19, 2012 11:59 am
Posts: 10
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
Professor

Joined: Sat Aug 31, 2013 9:15 am
Posts: 256
Re: Bubble Sorting
Do you mean a bubble sort with 100 different numbers? If so, that's easy. You just change MAX_NUMBERS to 100, make an array with 100 elements, and put whatever data you want in them.

_________________
FTC Team 6100 Chariots of Fire - Programmer (2012-2013)
FTC Team 7468 Blue Chariots of Fire - Programmer (2013-2014)
FTC Team 7468 Blue Chariots of Fire - Mentor (2014-2015)
Check out our team website at http://bluechariotsoffire.com/.

Thu Jan 01, 2015 12:46 pm
Display posts from previous:  Sort by
 Page 1 of 2 [ 16 posts ] Go to page 1, 2  Next

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge    2014 Robotics Academy Summer of Learning