This is a continuation of the article “WonderBuilders Module Contributions,” written by Wonderland Architect and WonderBuilder partner, Jonathan Kaplan.
WonderBuilders Module Contributions – Sorting Algorithm Module for CS Education
By Jonathan Kaplan
Unlike the modules described in the previous post, which are applications or utilities that are intended for all Wonderland users, the Sorting Algorithms module is a special-purpose tool for use in Computer Science education. This application was inspired by the seminal algorithm animation work of Computer Science Professor Bob Sedgewick and his student Marc Brown, who Nicole worked with while at Brown University in the 1980s (see “Survey of Algorithm Animation Platforms“).
We created this module to demonstrate the utility of curriculum-specific interactive tools that can be easily added into a generic Wonderland installation. This particular module combines both 2D and 3D elements, integrating a multi-user Java code editor for writing sorting algorithms with a grid of 3D spheres that are the target of the sort operation.
Once you have installed the module on your Wonderland server, select “Object” from the Insert menu, select “Sorting Demo” from the list, and then click the “Insert” button. You will see a code editor window plus 8 red spheres.
Initial Sorting Algorithm configuration.
Right-click on the editor window to “Take Control” of the application. Type in the code for your algorithm, noticing that a bit of the code is already written for you so that you can focus solely on the algorithm. For those of you who are not programmers, there are two sorting algorithms at the end of this post that you can copy and paste into the code editor for experimentation purposes.
Running a simple sort algorithm.
Using the tool palette, you can click on the right arrow tool to step through your code one line at a time. As you do, you’ll notice that cubes indicate which items in the set are being compared or swapped. Alternatively, you can click on the play button to run the sort. You can stop or pause this playback at any time. The randomize tool (second from the right) allows you to create a new random ordering of the objects. Notice that the two fields below the code pane provide information about the highlighted items and also about the overall gets and swaps.
If you wish to sort more than 8 items, click on the gears tool to open the sort settings dialog (we didn’t have a “settings” icon, so I used the “unsync” icon in a pinch).
Changing the settings to add more elements.
These settings also allow you to change the color, size, and spacing of the spheres, as well as randomize the objects.
Try comparing two different sorting algorithms by inserting another copy of the Sort Demo into the world and entering different code.
Comparing two sort algorithms.
With two people, you can click play at the same time and see which algorithm runs faster. Or two or more people can work on developing an algorithm together, either using the same code editor window, or using multiple windows side-by-side. It’s a perfect way to do remote pair programming.
In thinking about how this would be used in a class, an instructor can easily add instructional content to the world in the form of PDF or Open Office documents, give lectures in the virtual space, and walk around the space as multiple groups of students work on algorithm assignments. The virtual space allows the instructor to watch as students work, providing help when necessary. The addition of an in-world web browser can provide students with easy access to reference materials, or students can take advantage of the new Screen Sharer module described in the previous post to share content from their own computers.
In the future, we hope to see entire courses being taught in Wonderland worlds using a combination of the standard features and custom modules such as this one.
Jonathan Kaplan
Partner, Wonderland Architect, WonderBuilders LLC
Bubble Sort Algorithm
// bubble sort code
for (int i = s.getCount() - 1; i >= 0; i--) {
for (int j = 0; j s.get(j + 1)) {
pause(j, j+1);
s.swap(j, j + 1);
pause(j, j + 1);
}
}
}
Quicksort Algorithm
// quicksort code
int lo = min;
int hi = max;
pause(lo, hi);
if (lo >= hi) {
return;
} else if (lo == hi - 1) {
if (s.get(lo) > s.get(hi)) {
s.swap(lo, hi);
}
return;
}
int middle = (lo + hi) /2;
int pivot = s.get(middle);
pause(middle);
s.swap(middle, hi);
while (lo < hi) {
while (s.get(lo) <= pivot && lo < hi) {
lo++;
pause(max, lo, hi);
}
while (pivot <= s.get(hi) && lo < hi) {
hi--;
pause(max, lo, hi);
}
pause(max, lo, hi);
if( lo < hi ) {
s.swap(lo, hi);
}
}
pause(hi, max);
s.swap(hi, max);
sort(s, min, lo-1);
sort(s, hi+1, max);
Posted by Nicole Yankelovich 
