Step 6: Performing a Selection Sort

A selection sort algorithm goes through each item in the unsorted list one by one, and checks to see if the item is the smallest it can find, and then it takes that item and puts it in a new sorted list. It then repeats this process to find the next smallest item in the unsorted list, and places it next to the first smallest item in the sorted list. It will continue to repeat this process until the sorted list is complete and ordered from smallest to largest.

To do this we'll go through the list of rectangles comparing the height of the rectangles in the list to each other, and we'll colour the shortest rectangle red. Each rectangle will light up blue as it is checked so that we can see the program scanning through the list. Then once we've gove through the list comparing each rectangle to every other rectangle, the shortest rectangle will be coloured green and moved to the end of the list. Then we'll go through this process again, and keep repeating it until all the rectangles are ordered.

We'll start by creating a few property number variables for keeping track of important information. Set "Length of unsorted section" to the length of the list of rectangles, and set "total query time", and "queries for this pass" both to 0. By keeping track of how many queries the algorithm has performed, we can measure some of the cost of the algorithm.

Then we'll create two local instance variables for rectangle 1 and rectangle 2, and we'll call a new function that will compare these rectangles to each other. Name the function "compare rectangles".

Set rectangle 1 to the first rectangle in the list of rectangles, and set rectangle 2 to the second rectangle in that list.

Then in the "compare rectangles" function, click on the cog to add some input variables (a.k.a parameters). Create two new inputs and name them "rectangle 1" and "rectangle 2".

Then grab "instance rectangle 1" and "instance rectangle 2" (from the Local section of Variables) and drag them into their slots in the function call.

Now the "compare rectangles" function can take data from two instances which we can select each time we call this function.

Inside the "compare rectangles" function, we want to compare the height of the rectangles. We'll keep track of which rectangle is shortest, and then move on to compare the current shortest rectangle to the next rectangle in the list. Once we've gone through the whole list and there are no more rectangles to compare against, we'll move the smallest rectangle to the end of the list.

Since each comparison counts as a query, we'll increase the count of "queries for this pass" by 1.

To make sure we still have rectangles to compare, we'll check if the number of queries for this pass is smaller than the length of the unsorted section (since we don't want to keep comparing rectangles once we've hit the end of the unsorted part of the list).

Now inside this if-statement we will compare the height of rectangles to each other. If the height of rectangle 1 is larger than rectangle 2, store rectangle 1 as the small rectangle and store rectangle 2 as the large rectangle (make new local variables for small rectangle and large rectangle).

Modify this if statement to an if-else-if statement to check if the height of rectangle 1 is larger than the height of rectangle 2, and set the small and large rectangles accordingly.

Then we can colour the small rectangle red and the large rectangle blue, and keep track of the position of the smallest rectangle at this point (make a new property number variable for this).

Then we can move on to the next comparison. To make sure the next comparison happens as quickly as the query speed, make sure to use a millseconds delay block with the "milliseconds it takes to query the list" block used instead of a number block.

So that the whole list doesn't remain blue, switch the colour of the large rectangle back to grey.

Then we can perform the next comparison. Set the input rectangle 1 to the small rectangle, and rectangle 2 to the rectangle in the list that's position corresponds with the number of queries for this pass + 2.

Lastly, if the amount of queries for this pass is not smaller than the length of the unsorted section then we know that we've reached the end of the unsorted section. This means we can move the smallest rectangle to the end of the list, and start a new round of comparisons from the beginning.

Modify the if-statement for "queries for this pass < length of unsorted section" so that it's an if-else block (by clicking on the cog). Then create a new function named "move smallest rectangle to the end and search for the next" and drag the function call inside the else section.

In this function we'll set the colour of the smallest rectangle to green (to show that it has been sorted).

Then we'll use these two blocks (from Operators) to add it to the end of the list, while also removing it from its current position.

Then call the function to move rectangles x positions to match their list positions.

Also decrease the length of unsorted section by 1, increase total comparisons by queries for this pass, and set queries for this pass back to 0.

Finally, we'll check if the length of the unsorted section is greater than 0. If it is, that means there's still sorting to be done, so we'll call the compare rectangles function and compare the first two rectangles in the list against each other. If the length of the unsorted section is not greater than 0, that means the whole list has been sorted, so we can tell the user how long the process took.

Grab an "if" block and turn it into an "if-else" block. Check if the length of the unsorted section is greater than 0.

Then run the compare rectangles function to compare the first rectangle in the list with the second rectangle in the list.

In the else section, delay for 100 milliseconds, and then print out a message with the amount of comparisons.

Play the game to see the selection sort in action! How many comparisons did it take?