Insertion Sort

8-20-2018
A sorting method is required for almost every high score routine. Once we determine that player’s score.

For my game, I chose the Insertion sort. While not the quickest type of sort, it’s still pretty efficient, does not take up additional memory and it’s fairly small and short making it memory friendly. It is also non-recursive which also makes it memory friendly, as it won’t fill up the stack. I personally love the simplicity of the insertion sort routine.

In writing our sort function, we need to make sure not to only sort the numbers of the scores, but that the names move with those scores as well. If incorrectly written, we will assign wrong initials to a score. Nothing will upset a player more than to give your score to someone else.

Here is our function.

void insertionSort()
{
char hiTemp[4];
i = 0;
j = 0;
for(i = 1; i scores[j].hiScoreList && j >= 0)
{
//swap scores
scores[j + 1].hiScoreList = scores[j].hiScoreList;
//copy initials
strcpy(scores[j + 1].hiInitals, scores[j].hiInitals);
-- j;
}
scores[j + 1].hiScoreList = key;// place temp value in slot
strcpy(scores[j + 1].hiInitals, hiTemp);
}

Let’s do some explanations.

First, I’m going to create a temporary array.

char hiTemp[4];

This temporary array is used to store the initials of the player in the sorting. This will allow the move of the initials when the score is moved.

We initialize our I and j variables.

i = 0;
j = 0;

Now, let’s set up the loop that we are going to sort with

for(i = 1; i < 6; i++)

We are starting with 1 instead of 0, because of the usage of the variable j, which is always 1 off from i.

Within that loop, we are going to be doing a number of actions.

key = scores[i].hiScoreList;

Is a temporary value that stores the score being sorted.

strcpy(hiTemp, scores[i].hiInitals);//copies the value of initials[i] to hiTemp

Here, we are now copying the initials of the player in a temporary slot.

j = i - 1;

And now we are setting up our j variable.

while( key > scores[j].hiScoreList && j >= 0)
{
//swap scores
scores[j + 1].hiScoreList = scores[j].hiScoreList;
//copy initials
strcpy(scores[j + 1].hiInitals, scores[j].hiInitals);
-- j;
}

This is where the action starts happening and one of the nicer things about insertion sort. First the real nice thin about insertion sort, you can sort in either ascending or descending by changing just the sign of the comparison.
For example
key > scores

Will sort from high to low, descending order, however, if you have

key < scores

It will sort from low to high, or ascending order.

Here, we want descending order.

Back to the action.

while( key > scores[j].hiScoreList && j >= 0)
{
//swap scores
scores[j + 1].hiScoreList = scores[j].hiScoreList;
//copy initials
strcpy(scores[j + 1].hiInitals, scores[j].hiInitals);
-- j;
}

If the key is less than the score, then we keep moving the key until it is not less than the score. When that happens we will then swap the score and then swap the initials of the player. Pretty neat.

scores[j + 1].hiScoreList = key;// place temp value in slot
strcpy(scores[j + 1].hiInitals, hiTemp);

This finishes our swapping until the loop runs out.

Insertion Sort is a wonderfully short, in place sort that runs fairly quick, while not the quickest in the world, it is more than adequate for short sorting.

Who would have though that sorting was so much fun.

Happy coding.