Bubble Sort?

For Flowcode users to discuss projects, flowcharts, and any other issues related to Flowcode 2 and 3.

Moderators: Benj, Mods

sptcarl
Flowcode V4 User
Posts: 34
Joined: Thu Feb 18, 2010 10:53 am
Has thanked: 3 times
Contact:

Bubble Sort?

Postby sptcarl » Wed Jan 12, 2011 12:25 am

I am working on a project that involves collecting the number of points scored on 12 individual devices. (A sort of amusement game)
So, I shall set up the hardware and software to scan the devices and read the SCORE values.

I have an array of the 12 variables, (SCORE [0] to SCORE [11]) these will hold the random score numbers from 0 to 20 inclusive.

I need to sort these numbers so that I end up with the top 3 highest sCORE values.

The index numbers belonging to the 3 highest SCORES will then be stored under variables called FIRST, SECOND and THIRD.

I have been told that I need to perform a Bubble Sort on the array, but since this involves C code, I haven't got a clue!

Can anyone please assist? (That's if you can understand what I'm trying to do!)

Thanks in advance,
Carl.

User avatar
medelec35
Valued Contributor
Valued Contributor
Posts: 8202
Joined: Sat May 05, 2007 2:27 pm
Location: Northamptonshire, UK
Has thanked: 2343 times
Been thanked: 3318 times
Contact:

Re: Bubble Sort?

Postby medelec35 » Sat Jan 15, 2011 4:12 pm

Hi sptcarl
Here is a Bubble Sort flowchart.
Not using C code, as I prefer to use non C
It does appear to work OK.
Not sure if value for the 1st loop is correct?
It may need to be increased to 12?
Attachments
Bubble sort V3 Flowcode.fcf
(4.5 KiB) Downloaded 189 times
These users thanked the author medelec35 for the post:
sptcarl (Sat Jan 15, 2011 7:24 pm)
Rating: 5.88%
 
Martin

If you read a post that is useful, please show appreciation by clicking on thumbs up Icon.

sptcarl
Flowcode V4 User
Posts: 34
Joined: Thu Feb 18, 2010 10:53 am
Has thanked: 3 times
Contact:

Re: Bubble Sort?

Postby sptcarl » Sat Jan 15, 2011 7:34 pm

Hey medelec, thanks for taking the time and trouble to look into this for me.
I'm not sure how to say this though, but it's not quite what I'm after!
It works fantastically to produce the top 3 highest score values, but it's the index numbers related to the score values that I need to equal the variables of FIRST, SECOND and THIRD.
Ill have a play around and see if I can work it our for myself now that I have the method.

Thanks again,
Carl.

User avatar
medelec35
Valued Contributor
Valued Contributor
Posts: 8202
Joined: Sat May 05, 2007 2:27 pm
Location: Northamptonshire, UK
Has thanked: 2343 times
Been thanked: 3318 times
Contact:

Re: Bubble Sort?

Postby medelec35 » Sat Jan 15, 2011 8:23 pm

sptcarl wrote:It works fantastically to produce the top 3 highest score values, but it's the index numbers related to the score values that I need to equal the variables of FIRST, SECOND and THIRD.
.
Sorry my mistake, slightly misread.
Since it bubble sorts the random numbers out for you in the correct order from lowest to highest, the index numbers will be FIRST=11, SECOND=10 and THIRD=9 every time (unless I am still misunderstanding of course).
If you get stuck, then just put the format of what you want the result to look like e.g FIRST=11
(since as stated above will index 11 always be the highest number, 10 = next highest etc.).
Then I can finish flowchart off for you.
Attached is the example.
Attachments
Bubble sort V3 Flowcode1.fcf
(4.5 KiB) Downloaded 167 times
Martin

If you read a post that is useful, please show appreciation by clicking on thumbs up Icon.

sptcarl
Flowcode V4 User
Posts: 34
Joined: Thu Feb 18, 2010 10:53 am
Has thanked: 3 times
Contact:

Re: Bubble Sort?

Postby sptcarl » Sat Jan 15, 2011 10:29 pm

Sorry mate, I think it's me, I'm terrible at explaining things!
We are getting closer, we are getting the index numbers, but like you say, the result always be 11, 10 and 9.

From your last example the result I need is:
FIRST = 4
SECOND = 2
THIRD = 9
i.e. the index numbers belonging to the scores with the top 3 highest values.

Sorry to be a pain mate, your help is greatly appreciated.
Carl.

User avatar
medelec35
Valued Contributor
Valued Contributor
Posts: 8202
Joined: Sat May 05, 2007 2:27 pm
Location: Northamptonshire, UK
Has thanked: 2343 times
Been thanked: 3318 times
Contact:

Re: Bubble Sort?

Postby medelec35 » Sat Jan 15, 2011 11:22 pm

Its just you wanted a bubble sort, and the purpose of that is to place a series of numbers in numerical order.
But I understand now..
Perhaps if you post a link of website(if it was a website of course) that mentioned bubble sort, then that could help.
Edit:
Could this be a course assignment since technically the program I posted does actually store index of highest number in FIRST etc.?
So if you was using it for your interest to make a game, then problem solved.
If however an assignment requires index of highest number without 1st sorting numbers by bubble sort, then problem not solved (unless they wanted you to think of bubble sorting numbers 1st of course). :p
Martin

If you read a post that is useful, please show appreciation by clicking on thumbs up Icon.

Spanish_dude
Posts: 594
Joined: Thu Sep 17, 2009 7:52 am
Location: Belgium
Has thanked: 63 times
Been thanked: 102 times
Contact:

Re: Bubble Sort?

Postby Spanish_dude » Mon Jan 17, 2011 10:53 pm

You should try the binary sort algorithm.

Bubble sort works great, but it needs to check the whole array again and again.
I know that for something like this there's no need for improvement, but, it could be interesting to take a look at.

Anyways,

If you start a sort algorithm It will change the place of the scores, but it won't take the position with it. Here's an example of it:
So let's say you have an array like this:
{12, 30, 30, 120, 49, 56, 23, ...} with 12 being the score of the 1st game you read and 23 the score of the 7th game.

If you sort the scores from high to low you'll have something like this:
{120, 56, 49, 30, 30, 23, 12, ...}
So now, the score of the 1st game is 120 and that's not correct, that's not what you want to do.
(Correct me if I'm wrong, but that's what I understood from your posts)

What you would like to do is:
- Read 12 scores and store them into some array
- Check the array for highest score and store the position of the highest score into another array, and the value of the highest score into another one.
- Check the array for 2nd highest score ...
- Check the array for 3rd highest score ...

You don't have to use any sort algorithm for that as you want to know who or better said, which game has the highest score. Is it the 2nd score you read or the 11th one?

I'd see something more like this :

Code: Select all

char i = 0, j = 0, dummy_var = 0;
char read_scores[12] = {0};
char highest_score[3] = {0};
char position[3] = {0};

// read scores and store them in read_scores array

for (i = 0; i < 3; i++) // loop 3 times to get the position and value of the 3 highest scores
{
    for (j = 0; j < 12; j++) // loop 12 times to check the whole array for the highest score
    {
        // check if the score on position 'j' in the read_score array is higher than the value of the dummy variable
        if (read_scores[j] > dummy_var)
        {
            position[i] = j; // if so store the value of 'j' (the position) into the position array
            dummy_var = read_scores[j]; // store the value of the score into the dummy_var
        }
    }

    highest_score[i] = read_scores[position[i]]; // store the value of the highest score into the highest_score array
    read_scores[position[i]] = 0; //delete the value of the highest score so you won't read the same position twice
    dummy_var = 0; // reset the dummy var
}


So what do you want to do with that ? Send to the PC, or print it on a LCD screen ?

I'll show you how to write on the LCD.
The functions I'll use will not be correct, but you'll understand it to program that into your flowcode file.
Btw, every piece of code I have written until now can be done without any C-block icon (or whatever it's called), so it should be possible to simulate everything 8) .

Code: Select all

for (i = 0; i < 3; i++)
{
    LCD_ClearScreen(); // clear the screen
    LCD_SetCursor(0, 0); // set the LCD cursor on x=0 and y=0
    LCD_PrintString("Game : "); // write the string "Game : " on the LCD screen
    LCD_PrintNumber(position[i]); // write the number of the game
    LCD_SetCursor(0, 1); // set the LCD cursor on x=0 and y=1
    LCD_PrintString("Score : "); // write the string "Score : " on the LCD screen
    LCD_PrintNumber(highest_score[i]); // write the highest score of that game
    // wait 10 second before doing anything else, so you have the time to read who won and with how much points
    delay_s(10);

    //You could do this differently but, ok, that's the (easy) way I'd do it.
}


So this piece of code will write on the LCD screen something like this (it's an example):
Game : 4
Score : 125


That's it. No bubble sort algorithm. Just basic if-statements with for loops and some variables and arrays :mrgreen: .

Rgds,

Nicolas L. F.
These users thanked the author Spanish_dude for the post:
medelec35 (Sat Jan 22, 2011 10:00 pm)
Rating: 5.88%
 

sptcarl
Flowcode V4 User
Posts: 34
Joined: Thu Feb 18, 2010 10:53 am
Has thanked: 3 times
Contact:

Re: Bubble Sort?

Postby sptcarl » Thu Jan 20, 2011 7:25 pm

Sorry for not replying sooner guys, I've been away on business to Paris.

OK, I shall try and explain what I am trying to do...

I am the electronic designer at the company that makes the fairground/amusement park game where a group of players compete against each other by rolling balls into holes to make models (horses, camels etc) race a long a track. (you will either know it or you won't!)
Over the years I've developed the control gear from its electro-mechanical beginnings, through to dedicated CMOS 4000 series logic chip control, and now Im gradually converting it to be totally dependant on PIC based circuits.
Flowcode is my first experience of programming, both as a hobby and at a professional level, so I am still learning as I go along.

The project that Im working on at the moment is for a fully automated version of the game. As the race progresses, this will continually update 3 double digit LED displays, each display showing which player is FIRST, SECOND and THIRD in the race.
The players score points everytime they roll a ball into a hole, requiring 20 points to win the race. It is these points that this PIC program needs to continually read, calculate who is first, second and third, and then send the player numbers to the relevant displays.
The actual number of points is not required outside of the program.

Medelec, it was one of my mates who mentioned the bubble sort idea, over a few pints one night! He is more mathematically minded, confusing me with talk of Excell and spreadsheets!

Nicholas, thanks for your input, I do believe that what you have done there would be what I needed, but sadly all that C coding has just gone completely over my head.

Carl.

User avatar
medelec35
Valued Contributor
Valued Contributor
Posts: 8202
Joined: Sat May 05, 2007 2:27 pm
Location: Northamptonshire, UK
Has thanked: 2343 times
Been thanked: 3318 times
Contact:

Re: Bubble Sort?

Postby medelec35 » Thu Jan 20, 2011 9:27 pm

Hiya Carl.
Now I understand ( I can be a bit slow sometimes, I blame my age :P ). I was concentrating on bubble sort for you, but Since that was just an idea over some pints, and not a must( as I thought you wanted it base on that), Nicolas has a smart idea that will work for you.
So as a joint effort between Nicolas (as this is using his idea) and myself , here is a flowcode version that stores the position's of highest number in FIRST = 4, next highest in SECOND = 2 third highest in THIRD = 9 in the posted Flowchart. It also stores the highest three values if required.

Score sort V3 Flowcode2 is with LED displays added. Can only add 2 lots of dual display, so last two not used. way LEDS display may not be exactly what your after, but its a staring point.
LED part will not simulate well, needs to run on hardware (untested).
I will see if I can test it tomorrow in a different simulator.

Configuration settings, target device and target speed needs to be tailored for your own specific requirements.
Regards
Martin
Attachments
Score sort V3 Flowcode2.fcf
(8.5 KiB) Downloaded 159 times
Score sort V3 Flowcode1.fcf
(12 KiB) Downloaded 158 times
Martin

If you read a post that is useful, please show appreciation by clicking on thumbs up Icon.

sptcarl
Flowcode V4 User
Posts: 34
Joined: Thu Feb 18, 2010 10:53 am
Has thanked: 3 times
Contact:

Re: Bubble Sort?

Postby sptcarl » Fri Jan 21, 2011 11:24 am

Cheers Martin, you're a star. (Nicolas too)
Had a quick look over it and all looks great.
I shall study it later when I've got a bit more time, and let you know.

Thanks again,
Carl.

User avatar
medelec35
Valued Contributor
Valued Contributor
Posts: 8202
Joined: Sat May 05, 2007 2:27 pm
Location: Northamptonshire, UK
Has thanked: 2343 times
Been thanked: 3318 times
Contact:

Re: Bubble Sort?

Postby medelec35 » Fri Jan 21, 2011 9:37 pm

Changed Timer0 interrupt frequency and macro to get LED's to display correctly. For display I have only got one Eblock EB008 = quad 7seg. So can only see four digits light up, and they were fine. I can clearly see numbers 1428, using ports A and B. There are enough ports on 16F88 to display on eight 7 Seg LED's
Attachments
Score sort V3 Flowcode3.fcf
(14.5 KiB) Downloaded 171 times
Martin

If you read a post that is useful, please show appreciation by clicking on thumbs up Icon.

Spanish_dude
Posts: 594
Joined: Thu Sep 17, 2009 7:52 am
Location: Belgium
Has thanked: 63 times
Been thanked: 102 times
Contact:

Re: Bubble Sort?

Postby Spanish_dude » Sat Jan 22, 2011 9:55 pm

@medelec : You're fcf looks pretty good to me ^^

@sptcarl : You're welcome