ROBOTC.net forums - View topic

View unanswered posts | View active topics

It is currently Wed May 22, 2013 8:36 am

Bubble Sorting

Moderators: mightor, starwarslegokid, miki

Page 1 of 1

[ 14 posts ]

Print view

Previous topic | Next topic

Bubble Sorting

Author

Message

Simon1

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

mightor

Moderator

Joined: Wed Mar 05, 2008 8:14 am
Posts: 2864
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

_________________
| Some people, when confronted with a problem, think, "I know, I'll use threads,"
| and then two they hav erpoblesms. (@nedbat)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]

Mon Jul 23, 2012 2:43 pm

JohnWatson

Site Admin

Joined: Thu May 24, 2012 12:15 pm
Posts: 386

Re: Bubble Sorting

Now, that's just good luck...

_________________
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

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

Simon1

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

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

Simon1

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

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

Simon1

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. :crying:

Can someone explain to me how to implement it? I'm so confused.. haha.

Tue Jul 24, 2012 11:44 am

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

Simon1

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

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

MHTS

Guru

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1023

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

Simon1

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

Page 1 of 1

[ 14 posts ]

Who is online

Users browsing this forum: No registered users and 3 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

Jump to: