Quicksort Proficiency Exercise Help Page

This exercise asks you to reproduce the high-level behavior of the Quicksort algorithm on a random sequence of 10 values. Initially you will be presented with an array of numbers. Follow the steps below to complete the exercise.

Steps:

1. Select the pivot
1. Add the index number of the right-most element in the list with the index of the left-most element and divide by 2.
2. If necessary, truncate the result (drop the decimal value) to create an integer.
3. This integer is the index of the pivot. Click it.


2. Move the pivot to the end
• Click the right-most element of the list


3. Select the range to partition
1. Click an element to select it as the left bound. An blue indicator should appear above the value you selected.
2. Once the left bound has been set, click another element to select it as the right bound. An red indicator should appear above this value.


• If the list contains a single element, you must click it twice to set the left and right bounds on the same element. When you do a single purple indicator will appear above it.
• To change your bounds, simply click an element again to deselect it. Note: If the left and right bounds are set on the same element and you wish to move the left bound, you must move the right bound to another (temporary) location, move the left bound then move the right bound to its final location.


4. Partition the selected range
• Click 'Partition'.


5. Move the pivot to its final sorted location
• Scanning from the left and without passing the pivot, find the first element with a value greater than or equal to the pivot value. Click it.
• If all values to the left of the pivot and less than the pivot value, move on to the next step without clicking anything.


6. Mark the pivot as sorted
• If you followed the steps above properly, the pivot value will now be in its final sorted position. Click 'Mark Selected as Sorted'. The element will change color to indicate that it is sorted.


7. Repeat as necessary on sublists
1. If there are uncolored elements to the left of the sorted pivot element, repeat this process on the unsorted left sublist.
2. Once all values to the left are sorted, repeat the process as necessary on the unsorted right sublist.


• Always sort the left sublists before the right sublists.
• Note: If a sublist contains a single element, you may select it and immediately click 'Mark Selected as Sorted'.

Other Controls:

• If you want to back up a step and try again, click the "Undo" button.
• If you want to restart the exercise, click the "Reset" button.
• If you want to see the correct answer, click the "Model Answer" button to see a slideshow in a pop-up window.
• Note: Viewing the answer will prevent you from obtaining credit for the current problem instance. So just hit "reset" when you are done viewing the model answer.
• The button with gears on it will let you set some options such as the animation speed (for the slideshow model answer).
• The "About" button will tell you about who wrote this, etc.
• The "Help" button got you here.