Sorting Algorithm Module

September 25, 2010

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.

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.

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.

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.

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);
Advertisements

Wonderland Wednesday Community Showcase

July 7, 2010

Wonderland Wednesdays are weekly, developer-focused sessions that take place in the Wonderland community virtual world. Please refer to the Events tab on the Open Wonderland Facebook page for details. This week’s Wonderland Wednesday will be on the topic of Subsnapshots. RSVPs are appreciated.

Community Showcase

By Ryan Babiuch, aka “jagwire,” University of Missouri

Since its inception in March, Wonderland Wednesdays have provided developers in the Open Wonderland community with the opportunity to meet live with other developers to both learn about Open Wonderland and get to know each other. On Wednesday, June 23rd Open Wonderland developers were given the opportunity to showcase their work to the rest of the community for the first time. Of those developing in Wonderland, Jonathan Kaplan, Morris Ford, and myself attended on Wednesday to show the community what we have been working on.

First to present was Morris with his work on integrating scripting into Open Wonderland, specifically with animating models created using Autodesk Maya. He first showed a clock with movable hands which kept real time by receiving data from an outside source. Morris then provided to the community an animated bug moving through the world while flapping its wings.

Animated clock and bug modules

Animated clock and bug modules

Next up to present was Jonathan Kaplan. Jonathan has been working on a tool  for Computer Science students. Students can experiment with writing sorting algorithms in the multi-user code editor, or instructors can insert code for different sorting algorithms in order to show students visualizations of the various algorithms. The visualization involves a grid of spheres of different shades that are sorted from darkest to lightest. The first algorithm he showed was Bubble Sort, which is a slow but easy-to-understand algorithm for students beginning computer science studies. While that demonstration was working, another instance of the same module was used to display Quicksort, a much faster algorithm than Bubble Sort. Showing the two visualizations side-by-side, one is quickly able to deduce that Quicksort is substantially faster than Bubble Sort.

Quicksort on the left, Bubble Sort on the right

Quicksort on the left, Bubble Sort on the right. Students use the control panel to run the program or step through it one instruction at a time. The line of code being executed is highlighted in the code window while cubes highlight the spheres currently being inspected or swapped.

Control window displayed for Quicksort (on left)

The Sort Settings window allows students to change the number of items being sorted, randomize the grid, and change several visual attributes.

I was the final presenter. I first showed two new tutorials I have been working on. The first tutorial acts as a supplement to Jordan Slott’s “Developing a new cell” tutorial series. My first tutorial aims to add a simple spinning animation to the previously created cell. The second tutorial continues where the first leaves off and describes how to add security to the cell. With the two tutorials, I also presented a custom ContentImporter implementation for PDFs. The content importer acts as a way to submit files to the content repository running on Wonderland servers without creating anything to be shown in-world.

PDFImporter.java plus new cell creation tutorials

From left to right: PDFImporter.java, Creating a new cell (part 5): Animating a cell, and Creating a new cell (part 6): Adding custom security to a cell

Next, I showed an Inventory module which allows Wonderland users to add  in-world objects to a virtual inventory. Users add objects to the inventory by clicking on objects which have an Inventory Component attached and choosing “take it” or “leave it for now” from a menu that pops up.

Clicking on the red sculpture presents the Inventory menu

Clicking on the red sculpture presents the Inventory menu

Sculpture disappears after being taken

After clicking "Take It", the red sculpture disappears from the world and reappears inside the inventory window. Clicking the remove button will make the red sculpture leave the inventory and reappear in-world.

After presenting the virtual inventory, I show the “spatial affordances” that I developed for the iSocial project. (Editors Note: The term “affordance” is used in relation to Wonderland in a variety of contexts. If you are unfamiliar with the term, the essay Affordances and Design by Don Norman provides a detailed explanation of the term.) The spatial affordances act as ways to either keep users in a designated space, or keep users out of other spaces. The affordances are displayed as discs appearing on the ground to keep users within and red vertical squares which act as Force Fields.

A red force field is blocking access to the red sculpture and the mouse.

A red Force Field is blocking access to the red sculpture and the mouse.

Clicking unlock from the context menu allows your avatar to walk through the force field.

Selecting "unlock" from the context menu allows your avatar to walk through the Force Field.

Personal Pods, which denote places for users to stand, are another type of spatial affordance.

Personal pods (pedestal shown in green) denote areas for which a person should sit/stand similar to a chair or desk.

Personal Pods (pedestal shown in green) denote areas for which a person should sit/stand similar to a chair or desk.

Pod turns red when person is on it

When a user stands on a Personal Pod, it turns red to show that the user cannot move outside of the bounds of the Pod. It also shows that no one else can occupy that Pod.

Pod unlocked

Right clicking and selecting "unlock" from the context menu turns the Pod yellow while in transition to green. Once the Pod turns green, the user is free to move from the Pod.

Pod is green

With the Pod green and the user no longer occupying the Pod space, another user can walk onto the Pod.

This first showcase was a great success and everyone in attendance was excited to see what other developers were doing with the Open Wonderland toolkit. We hope this will be the first in a series, so please let me know if you have a module you would like to demonstrate so I can set up the next community showcase session.


%d bloggers like this: