Help (1 Viewer)

[nakappe]

I really need help with this question. I have no knowledge with algorithm, and if anyone could please help me with this question I might be able to get some ideas about it. So here is the question below.

Below is a High Score table in a game.
1. Charlie 21
2. Bill 11
3. Lucy 10
4. Chris 5
5. Col 4

Sam has just completed the game and scored 15 points. Write an algorithm which checks whether Sam's score has made into the High Score table and if so sorts the table and prints a new high score table.

Im guessing you use the Bubble sort method, but i dont know how to. Please help.

Thank you in advance.

 

[Drdusk]

To write this algorithm you firstly have to determine whether his score is high enough to be placed on the HighScore table.
For this to be the case his score must be higher than the lowest score.

Remember to always consider the variables before anything else.

Let Sam's score be called NewScore, and let Valid be True if its high enough and False if it isn't

To determine whether his score is large enough for the leaderboard we would need something like:


Valid = False
IF NewScore > HighScore(5)
....Valid = True
....HighScore(5) = NewScore
ENDIF

Now our problem is that Sam's score is on the last position on the leaderboard but what if its higher than the scores above it?
This part is really simple because we can already assume the rest of the scores are in order, so all we have to do is move Sam's score up an index if his score is greater than the index above.

Now we would need a variable called Position that is true if Sam's score is in the correct position and false if it isn't, and a variable Index that tells us the Index of Sam's Score.
Hence the full algorithm:

BEGIN ALGORITHM
....Index = 5 //As Sam's score or any NewScore will always begin at the bottom
....Position = False
....Valid = False
....IF NewScore > Highscore(5)
........Valid = True
........Highscore(5) = NewScore
....ENDIF
....IF Valid = True
........WHILE Position = False AND Index <> 1 //If Sam's score is first place, it wont undergo the Sort
............IF NewScore > Highscore(Index - 1) //Swaps Sam's score with the one above if his is greater
................Swap(Highscore(Index),HighScore(Index - 1)) ]//Standard Swap subroutine
................Index = Index - 1 //Index of Sam's score will reduce by 1 every time the Swap occures
............ELSE
................Position = True
............ENDIF
........ENDWHILE
....ENDIF
END ALGORITHM

//Note this is a Standard Swap algorithm that you should know off by heart!
BEGIN Swap(HighScore(Index),HighScore(Index - 1))
....Temp = HighScore(Index)
....Highscore(Index) = Highscore(Index-1)
....Highscore(Index - 1) = Temp
END Swap(HighScore(Index),HighScore(Index - 1))

 

[nakappe]

Thank you so much for your help. Although I don't understand the algorithm fully, and in the case of this question, the score should be 15 instead of 5, correct? And if you could, please provide further explanations if possible. Sorry in advance for my low capabilities.

 

[Drdusk]

All good, I wouldn't say low capabilities, everyone starts somewhere but you can control where you end up!

With regards to my answer what don't you get?

1) The actual lines of the algorithm, i.e. the syntax and what a line means, OR

2) The functionality/purpose of parts of the algorithm with regards to how it helps in the answer.

If its (1) then read the Software course specifications as I said earlier as they will clear it all up for you.


If its (2) then could you please point to any parts of the algorithm and be fully open/detailed with your response as to what you don't get and I'll get to you

 

[nakappe]

Thank you, I'm too confused to the point where I dont even know what I dont get, its basically everything, and the fact that the Index = 5 makes it more confusing as I thought it would be set to 15 as Sam scored 15 points. And the rest of the algorithm is just full of confusion to me so if you could, please explain each line and the functionality/purpose of the algorithm. Again, thank you so much for your support I really appreciate it.

p.s. I know what a bubble sort is and how it works, but I want to know how you can write that in an algorithm in order to check if Sam's score of 15 can make into the list, and if so, sorts the table and prints a new one.

 

[Drdusk]

Thank you, I'm too confused to the point where I dont even know what I dont get, its basically everything, and the fact that the Index = 5 makes it more confusing as I thought it would be set to 15 as Sam scored 15 points. And the rest of the algorithm is just full of confusion to me so if you could, please explain each line and the functionality/purpose of the algorithm. Again, thank you so much for your support I really appreciate it.

p.s. I know what a bubble sort is and how it works, but I want to know how you can write that in an algorithm in order to check if Sam's score of 15 can make into the list, and if so, sorts the table and prints a new one.

No worries, glad to help.

Index is not actually Sam's score, rather it is the POSITION of his score in the Highscore array.

For example at the start Highscore(Index) = 15 where 15 is Sam's score and it is placed in the 5th position in the array, because remember Index = 5.


Now in all honesty if your that confused no amount of me explaining will help. I recommended you start with an easier algorithm because if I recall correctly now this was a past HSC algorithm that was worth like 4 marks.


If you go on ATAR notes and go to the Software Design and development section, there was a competition known as ALCON which I actually did one round of myself :c


The algorithms in that were probably easier than this so I recommended you try them, and also make sure you read chapter 4 of the Sam Davis textbook


A small bit of advice my software teacher gave me when I was struggling badly with algorithms was that no amount of anyone explaining an algorithm to you will suddenly make it all click in your brain. You kind of just have to sit and think through it logically and figure it out. However I will try and explain to you in the next post.


However this only applies if your that confused with it, once you start getting better other peoples explanations can get through to you.


Now with the bubble sort:

A bubble sort just looks at adjacent elements and swaps them if they're out of order. This algorithm is basically a very simple bubble sort because all it does is checks Sam's score with the score of the Index above it and swaps if Sam's score is larger.

 

[Drdusk]

Explanation:
P.S. This is going to be really long!

So we start with Index = 5, Position = False and Valid = False. Now the way this algorithm works is it checks Sam's score, i.e. NewScore with HighScore(5) which is the last score on the leaderboard BEFORE Sam's score is added. Then if Sam's score is greater, it copies Sam's score into the 5th position of the array Highscore. Valid = True means Sam's score has made it onto the leaderboard, and Valid = false means it hasn't. Now consider this code:

IF NewScore > Highscore(5)
........Valid = True
........Highscore(5) = NewScore
....ENDIF

See the first line says "Is Sam's score greater than the last score in the array Highscore?" which in this case is Col's score of 4. Well yes Sam's score is 15 and therefore his score is definitely large enough to make it onto the leaderboard! So since his score is large enough we set Valid = true, now this is particularly important because if you look at the next line of code right after it begins with
IF Valid = true. This is there to ensure that our simplified bubble sort only occurs IF Sam's score has made it onto the leaderboard, because there would be no point in performing a sort if Sam's score is too low.

Then Highscore(5) = Newscore just means we are setting the 5th position in the array Highscore to equal Sam's score.


Thus so far what have we done? Well we've decided that Sam's score is large enough to be on the leaderboard and thus we have placed his score in the last position because his score is at least guaranteed to be in last place.


Now onto the next part of the algorithm, this part is the most confusing so you must think through what I'm saying carefully.

We firstly see the line WHILE Position = False and Index <> 1. Now Position will equal True if Sam's score is in the correct position on the leaderboard and False if his score isn't in the correct position. However Sam's score is in last place at the moment but is it meant to belong there? His score is actually higher than Chris and Lucky for example!

Now we need the Position = False in the loop because we only want to swap the position of Sam's score WHILE his score is in the wrong place because why would we want to swap otherwise? The question asks us to put his score in the correct place.

Now the <> in Index <> 1 just means does not equal. This is relevant because suppose we've performed the sort a few times and Sam's score ends up in first place. There is no more positions in the array for us to swap Sam's position with. This is seen in the next line IF Newscore > Highscore(Index-1) as in this line we determine if Sam's score is larger than the one before it, but in first place there is no score before Sam's, and hence we need Index <> 1 in the While loop.

So in English it translates to "WHILE Sam's score is in the incorrect position AND his score isn't in first place"

Onto the next part, now this is the actually Physical Sort that you were talking about. It checks Sam's score with the one before it and if Sam's score is greater, his score is swapped as can be seen through the Swap subroutine.
However after the swap has occurred, Sam's score is in the different position right? So we must reduce the Index by 1, thus Index = Index - 1. Recall INDEX is the Position of Sam's score, so the position of his score will reduce by 1 in the array each time the swap occurs, and so right after the swap we do Index = Index - 1.

After that we are hit with ELSE, Position = True. The IF Statement IF Newscore > Highscore(Index - 1) is saying "IF Sam's score is greater than the one before it", but what if it isn't?? What if Sam's Score < Highscore(Index - 1)??

In that case it means Sam's score is actually in the correct position! because the rest of the array is already sorted and therefore if Sam's score is less than the one before it, it must also be less than every other score even before that.




AND Tada! There you have it!. The whole algorithm explained line by line in English. I hope you understand

EDIT: I almost threw my laptop in anger after this website logged me out right AFTER I finished typing everything. Luckily it was saved phew!

 

[nakappe]

Oh my god, I cannot appreciate you enough! Thank you so so so much for your time and effort into helping me out with this! I was able to not fully understand it yet, but get the idea of how this algorithm works!! I seriously was panicking during the Christmas holidays because even though I tried answering it, I couldn't even start because I don't know how anything works. Thank you so much again for your support, I really do appreciate it.