Step 5: Shuffling the list
Now we'll move on to Sorting algorithms. The two sorting algorithms we will look at are called Selection Sort and Quick Sort.
To try out these new sorting algorithms we will need an unsorted list. We'll create a shuffling function that will disorder the list.
We'll create a new level for the sorting algorithms. Drag this level in front of level 1 (to make sure it plays first).
The script in level 2 will start off by creating a list of rectangles just like in level 1, and since we've already created a function for that, we can simply copy that function. Go back to level 1, and open the script. Find the function named "create a list of rectangles and draw them", and click on it to select it. Press CTRL + C on your keyboard to copy these selected blocks.
Set up Level 2 just like we did with the first one: place a game object in the level, and add a script to it.
Now in the new script, press CTRL + V to paste the function that we copied before.
We'll run this function when the game object is created. We'll also create a couple of new number variables for "millseconds it takes to query the list" and "amount of shuffles left". Then in 100 milliseconds we'll run a new function named "shuffle the list".
This "shuffle the list" function will grab a random rectangle from the list, then remove it from the list and re-insert it at the end of the list. It will repeat that until there are no shuffles left (which explains why we set up the variable "amount of shuffles left").
To grab a random rectangle to shuffle, we'll first check if "amount of shuffles left" is greater than 0, and then we'll set a new local variable instance to shuffle. Grab the "if" block (from Control Flow), the ">" block (from Operators), the "number amount of shuffles left" block (from Variables), "0" (from Operators), and "set instance shuffled rectangle" (from the Local section of Variables). Connect these blocks together as shown below.
The shuffled rectangle will be selected and removed from a random position in the list of rectangles. Grab the "in list 'list list' get #" block (from Operators), and drag it into the instance variable block. Click on "list list" and change it to "list of rectangles", then click on "get" and change it to "get and remove".
The "#" slot will select a position in the list, and we can use a random number here. Grab the "random integer from 1 to 100" block (from Operators), "length of" (from Operators), and "list list of rectangles" (from Operators). Arrange the blocks as below.
Now that the "shuffled rectangle" has been selected at random and removed from the list, we need to reinsert it into the list. Grab the block "in list 'list list' add _ to the end" (from Operators), and "instance shuffled rectangle" (from the Local section of Variables). Connect those blocks as shown below, and change "list list" to "list list of rectangles".
Also change the amount of shuffles left by - 1.
The next thing we'll do is update the x-position of the rectangles to match their updated list positions. Create a new function and name it "Move rectangles x positions to match list positions". Grab the function call block for this function, and drag it under the latest block in the "shuffle the list" function.
We want to make this function loop through the list of rectangles, and count up by one each time it loops. Each time it counts up, it'll grab the next rectangle in the list, and position it a little further across. In here we'll make a new local number variable named "iterations" and set it to 0. Then grab a for-loop "i" (from Control Flow) and rename i to "rectangle in list". Grab "list list of rectangles" (from Variables) and connect it to the for-loop.
Inside the for-loop, set iterations to increase by 1.
Grab "true/false rectangle in list" (from the Local section of Variables) and change it to "instance rectangle in list". Then set the x position of this instance to 120 + (iterations x 10).
That completes this function. Now we can go back to looking at the rest of the shuffle function. Make it so that after the "move rectangles x positions..." function runs, in 10 milliseconds the "shuffle the list" function is called.
Now that we've told the shuffle function how to work, we need to get it to check if there are no shuffles left, and then to move on to the next step if that's true. Change the "if" to an "if-else-if" block by clicking on the cog icon and then drag the else-if block inside.
Click the cog icon again to dismiss this window. Check else-if "number amount of shuffles left" = 0, and then run a new function named "Perform selection sort algorithm".
Play your game now to see the shuffling working.
Now let's move on to making the selection sort algorithm.
