ROBOTC.net forums
http://www.robotc.net/forums/

Bubble Sorting
http://www.robotc.net/forums/viewtopic.php?f=1&t=4696
Page 1 of 2

Author:  Simon1 [ Mon Jul 23, 2012 2:36 pm ]
Post subject:  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!

Author:  mightor [ Mon Jul 23, 2012 2:43 pm ]
Post subject:  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

Author:  JohnWatson [ Mon Jul 23, 2012 3:49 pm ]
Post subject:  Re: Bubble Sorting

Now, that's just good luck... :D

Author:  MHTS [ Mon Jul 23, 2012 4:37 pm ]
Post subject:  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;
  }
}

Author:  Simon1 [ Tue Jul 24, 2012 11:08 am ]
Post subject:  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.

Author:  MHTS [ Tue Jul 24, 2012 11:19 am ]
Post subject:  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.

Author:  Simon1 [ Tue Jul 24, 2012 11:23 am ]
Post subject:  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;
    }
  }
}

Author:  MHTS [ Tue Jul 24, 2012 11:36 am ]
Post subject:  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;
            }
        }
    }
}

Author:  Simon1 [ Tue Jul 24, 2012 11:44 am ]
Post subject:  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.

Author:  MHTS [ Tue Jul 24, 2012 11:49 am ]
Post subject:  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;
        }
    }
}

Author:  Simon1 [ Tue Jul 24, 2012 11:54 am ]
Post subject:  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!!!

Author:  MHTS [ Tue Jul 24, 2012 11:56 am ]
Post subject:  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);
}

Author:  MHTS [ Tue Jul 24, 2012 12:03 pm ]
Post subject:  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);
    }
}

Author:  Simon1 [ Tue Jul 24, 2012 1:28 pm ]
Post subject:  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.

Author:  BurningLights [ Thu Jan 01, 2015 12:46 pm ]
Post subject:  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. :bigthumb:

Page 1 of 2 All times are UTC - 5 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/