Step 7: Performing a Quicksort
Quicksort is called "quicksort" because it is much more efficient than simple sorts like insertion sort. It doesn't slow down as quickly as insertion sort when used on very large lists.
Here's how a quicksort works:
- Take a list.
- If a list has 1 or 0 members, it is sorted and you can finish. Otherwise, continue.
- Pick a value called a "pivot". Compare every other value to the pivot.
- If a value is below the pivot value, put it on the "low" side of the pivot.
- If a value is above the pivot value, put it on the "high" side of the pivot.
- Quicksort the list of the low side.
- Quicksort the list of the high side.
As you might imagine, this process quickly breaks the initial list up into smaller and smaller pieces. This breaking up is called partitioning. Partitions are arranged in order lower to higher. Once a partition has just a single member, we know it's perfectly sorted, and we can stop repeating.
This repetition, where a function calls itself, is called recursion. It means several copies of a function can be running, nested inside themselves. It's very important to control recursion so it stops eventually, because otherwise it could run infinitely many times.
Because recursion is not a straightforward series of operations like an insertion sort, it is difficult to animate it. We will concentrate on making a quicksort that works instantly, rather than stepping through the process.
Setting Up
First of all, we have to set up some foundations for our scene. These will be similar to previous steps, but some aspects are different. Please follow closely.
First, make a new level and drag it in front of the other levels.
Then place an object (any object), and create a script on it. Call the script "Quicksorter".
Our setup will do these things:
- Hide the script object
- Note that the sort hasn't run
- Create a caption
- Describe how the sorted objects should be arranged
- Track performance
- Create an unsorted list of objects
First, create the Event block When created.
Add the Look block set visibility of myself to..., and set it to false. We only need to see the objects created by this script, not the initial object itself.
Create a variable property true/false called alreadyRun, and set it to false. We will use this later on to check whether the quicksort has run, because we don't want to run it twice.
Now we're going to make a text field to display the status of our algorithm. This will take several steps.
Create the Draw block create new textfield with text.... Assign the text to the message "Press SPACEBAR to quicksort".
Create the Draw block set text alignment of textfield to..., and set it to center.
Create the Draw block set font color of textfield to..., and set it to a nice dark gray, or some other colour that's easy to read.
Create the Transform block set x position of... to.... Set the X position of the textfield instance to 384. This is halfway across the screen, so the text will be fully centered.
Duplicate the set x position block, and set the Y position of the textfield instance to 64, close to the top of the screen.
Finally, textfield is a variable. If we want to use it later, we must set it as a property. Create a variable property instance called caption, and set it to textfield.
Next, we want to specify some arrangement parameters. These will be used later whenever we want to arrange our display objects. Each of these should be a property number.
Set arrangeSpacing to 10. This will be the distance between bars.
Set arrangeStartX to 120. This will be the left margin.
Set arrangeStartY to 200. This will be the top margin.
Set elements to 50. This will be the number of bars created.
Create another property number called comparisonCount, and set it to 0. We will increase this by 1 every time we do a comparison, so we can tell how much work the quicksort does.
Finally, create a function called populateData. Put a call to populateData at the end of the When created block. We will fill this function out in the next section.
Your When created block should now be finished. Check that it looks like this:
Play your game. You should see the message "Press SPACEBAR to quicksort". Nothing else will happen... yet.
Generating Scrambled Data
In this section, we will generate a list and mix it all up, so we have something to sort. We will do this by creating an ordered list of bars with height 101-150, then pull random elements out of that list and put them into another list, until the first list is empty. We will not animate this process.
Take the populateData function you created in the previous step.
Create a variable list called list and set it to the Operator block create empty list. This will be our source of ordered values.
Create a property list called data and set it to create empty list. This will be our final list. It is a property because it will be used elsewhere in the script.
Create the Control Flow block count with i from 1 to ... by 1. Change it to count to the elements property.
Inside the count block, create the Draw block create new rectangle with a width/height of.... Set its width to 5 and its height to 100 + i. This will create a series of bars, each slightly longer than the last.
Also inside the count block, create the Operator block in list... add... to the end. Ensure that it's using the variable list list you defined earlier. Now add rectangle to the end.
Outside and after the count block, create the Control Flow block repeat while.... Add the Operator blocks not and ... is empty (from the List section). Assemble these with the variable list to read repeat while not (list is empty). This will repeat until the list has no more values left.
Inside the while block, create the Operator block in list... add... to the end. Set the list to the property data which you created earlier. Add the Operator block in list... get..., use the variable list, and change the block to read get and remove and target random. This line should read in list data add (in list list get and remove random) to the end. This will take a random element out of the first list and add it to the second. This should give you a totally random order.
Finally, create a function called positionBars. We will fill this out in the next step. Add a call to positionBars to the end of populateData.
Your populateData function should now be finished. Check that it looks like this:
You will not see much if you play right now, because all the bars are piled up in the corner.
Displaying Data
In this step, we will spread out the bars in the order they appear in the data list. This is useful for viewing the list before and after it is sorted.
Take the positionBars function you created in the previous section.
Create the Control Flow block count with i from 1 to... by 1. Count to the Operator block length of data. All the other blocks go inside this one.
Set a variable instance rectangle to the Operator block in list... get #.... Access the property data at #i. This gives you a reference to the current rectangle. We do this because we will use it more than once later on, and it's more efficient to fold that access down into a single reference.
Create the Transform block set x position of... to.... Set the X position of rectangle to (i * arrangeSpacing) + arrangeStartX.
Duplicate the set x position block. Set the Y position of rectangle to arrangeStartY.
Your positionBars function is now finished.
Play your game. You should now see your bars arranged on screen. Because you have scrambled them, they will appear something like this:
Beginning To Sort
We want to run our operation when we press SPACEBAR. We will not fully complete this function just yet. We'll use it to demonstrate several intermediate steps.
Create the Event block when the player presses key.... Change this from presses to releases, so that we can't interrupt while a key is down. (This is unlikely in this script, but it might happen if you use a quicksort in another program.) Set the key to SPACEBAR.
Create the Control Flow block if... do. Add the Operator block not, and the property alreadyRun. Thus, no matter how many times you press SPACEBAR, you will only run the sort once. All the other blocks go inside this one.
Set alreadyRun to true. We might as well do this immediately.
Create the Draw block set text of... to.... Apply it to the property caption. For now, set the text to SPACEBAR pressed!.
Add a call to the function positionBars. This will display any changes you made to data on screen.
Run your game. If you press SPACEBAR, you should now see a confirmation message. The sort will not run yet... but now we're ready to see the result.
The Lomuto Partition
In this section, we'll explain our strategy for the rest of this chapter.
A quicksort operates by performing a partition into low and high values, then quicksorting each of those partitions. There are many ways to perform that partition. We'll be using an algorithm called the Lomuto Partition.
Lomuto Partition sets the pivot as the last term in a list. Then it counts up through the rest of the list, swapping low values down and keeping high values up. Finally, it swaps the pivot into the middle.
This could be a very complicated task, so we're going to do it backwards. This way, you can test everything, piece by piece.
First, we'll learn how to swap values in a list.
Then, we'll partition a list into low, pivot, and high sections, using the swap function.
Finally, we'll build a recursive quicksort algorithm using the partition function.
Swapping List Elements
In this section, we'll learn how to swap values in an array.
Create a function called swap. Open the cog section and add three parameters to the function, called list, a, and b. These parameters will tell the function to swap the elements at index a and index b within the list. Close the cog.
Here's what we're not going to do: set a to b, then b to a. Can you see why? We would lose the value of a immediately, so everything would become b. Instead, we'll store the values of a and b in variables, and set from those variables.
Set a variable instance called aInstance to the Operator block in list... get #.... Set the list to the variable list, and the # to a.
Duplicate that block, and create a new variable instance called bInstance. Set this to list # b.
Create the Operator block in list... set #... as.... Set the list to list, the # to a, and the value as bInstance.
Duplicate that block, and set # b as aInstance.
Now you've swapped the values of a and b.
You could be more efficient and skip creating aInstance. Just assign the value of b directly to a. We have done this longer example for clarity.
To test your swap function, insert a call in your SPACEBAR function. Insert a call to swap just after set alreadyRun. Fill in the parameters: list is data, a is 1, b is 50. Also change the set text to display "Swapped 1 and 50!".
Now, when you play and press SPACEBAR, you should see the first and last values switch places.
Partitioning List Segments
In this section, we will use our swap function to run the Lomuto partition, dividing values into low and high partitions.
Create a function with return, and name it partition. Add the parameters list, start, and end. These refer to the indices of the part of the list we want to partition.
Attention: This is not a regular function, but a function with return. Make sure you create the correct type.
Create a variable number called pivot. Set it to the Transform block actual height of the Operator block in list... get #.... Set the list to list, and the # to end (make sure list is of type list, and end is of type number). This is the value of the pivot, against which all other values will be compared. There is no particular need to choose any given pivot, but choosing either the start or the end means we have a solid list to step through, and if we choose the start, performance can be very bad on a sorted list. The end is thus a convenient choice.
Create a variable number called low. Set it to start (make sure start is of type number). This number will point to the top of the low part of the partitioned numbers. In fact, it points at the first high number. This means if we swap a low number into this place, it will put a low number on top of the low numbers, and pass a high number up to the top.
Create the Control Flow block count with i from... to... by 1. Change the name of the index from i to high. Count from start to end - 1. We do not count all the way to the pivot.
Inside the count block, create the Control Flow block if... do. Check if actual height of in list get # (end) is greater than (<=) pivot.
Inside the if block, add a call to swap. Set the parameters: list is list, a is low, and b is high.
Also inside the if block, set low to low + 1. When we swap a low value down, we increase the size of the low partition by 1.
Inside the count block but after the if block, set the property comparisonCount to comparisonCount + 1. Every time we check two list elements, we increase this count. This will tell us how much work the algorithm needed to do when we're finished.
Outside and after the count block, swap with parameters list, low, and end. This will swap the pivot in between the low and high partitions. Fun fact: the pivot is now perfectly sorted. It will not be considered in subsequent processes.
Finally, in the return slot at the end of the function, add low. This will point at the final location of the pivot.
You should now have a function that looks like this:
To test the partition, go back to your SPACEBAR function. Delete the call to swap. Create a variable number called pivotIndex.
Set pivotIndex to partition, with the parameters data, 1, and 50. Change the text message to Partitioned list!.
We must use a variable here, instead of calling partition directly, because it has a return value.
When you run the game, you should see something a little like this:
Quicksorting
In this section, we will finally complete the quicksort. We will build a recursive algorithm and see perfectly sorted data.
Create a function called quicksort. Add the parameters list, start, and end. Make sure these are of type list, number, and number when you access them later.
Create the Control Flow block if... do. Check whether start < end. If the start is equal to or greater than the end, you have a list segment with no length, and can quit without doing further work. Add all subsequent blocks inside this block.
Create a variable number called pivotIndex. Set it to the result of partition of list, start, end. Because the pivot index alone is guaranteed to be sorted, we want that number, so we can avoid it.
Now we're going to get recursive. Add a call to quicksort - the very function we're working on! Set its parameters to list, start, and pivotIndex - 1.
Add a second call to quicksort, with parameters list, pivotIndex + 1, and end.
This function is now complete.
Displaying Output
Now we're going to run the quicksort when we press SPACEBAR. Return to your SPACEBAR function once more.
Delete set pivotIndex to partition.
Add a call to quickstart, with the parameters data, 1, length of data.
Change the text value of caption. Use a create text with... block, and give it a total of 3 spaces. Set the values to "Quicksort complete! Made ", comparisonCount, and " comparisons.". For clarity, make sure there are spaces at the end of the first line and the start of the third line.
Now run your game. You should see it go from chaos...
... to order.
Congratulations! You've made a sorting algorithm.
If you want a challenge, try to write an animated quicksort of your own once you've finished this exercise.
Comparing Efficiency
Run your algorithm a few times. You should see results between about 200 and 300.
Compare this to the insertion sort! Can you see why it's called quicksort?
In fact, this is even more important than it seems. When you try to sort a larger list, it must compare more items against more items. An insertion sort will take time proportional to the number of list elements, squared. This means if a list is 10 times longer, it will take 100 times as much time! Quicksort will also slow down with more objects, but the effect is not as pronounced. In big applications, this can make impossibly long sorting operations go much faster.
There are many kinds of sort, with many different applications and kinds of performance.