Quicksort VR is a 3D visualization of a non-optimal, recursive quicksort algorithm implementation. It is written in JavaScript and HTML and uses the A-Frame framework
Quicksort VR is compatible with most modern browsers, including mobile Chrome.
Simply go to the live site from a browser and click to drag the white cursor onto the Continue block.
If you have a Google Cardboard, and are on a mobile device, press the button on the bottom left of the window and place your mobile device into the Google Cardboard. The white cursor follows your gaze, so simply turn your head to hover over the Continue block.
To continue, you must move the cursor away from the block, and then back onto the block. After continuing through the introduction, the demonstration will proceed to completion. To rerun it, refresh the page.
After selecting 'Continue' the first time, 12 blocks representing array elements will be randomly arranged and made visible. Their colors are generated by three out of phase sine waves providing rgb values equally spaced along one period.
The quicksort algorithm being visualized here is a recursive algorithm, and is certainly not an optimal implementation of quicksort.
Each group of elements to be sorted is modeled as an instance of the SortingTreeNode class. This instance contains information about its center position, whether it is sorted, references to its parent and child nodes, a reference to its pivot element if it has one, and a reference to its non-sorted elements.
The algorithm selects the first element of the array as the pivot element, and compares each remaining element to this pivot element. Elements with a lesser value (represented by a smaller block) will be moved to the current node's left node, and larger elements are moved to the right. These left and right nodes are then sorted the same way if they have 2 or more elements in them. If they have one or less elements, they are considered sorted (the base case), and are skipped. When both side nodes of a node are sorted, the side nodes are concatenated with the pivot element, and the algorithm will move on to the parent node. If there is no parent node, that meanst the algorithm is at the root of the tree, and after sorting the root node it will know that it is finished.
Since QuickSort VR is built using A-Frame, it is able to change the camera's perspective based on a mobile device's rotational sensors (accelerometer, gyroscope). When visiting the site on a desktop or laptop that does not have these sensors, the camera's orientation is controlled by grabbing and dragging the screen with a mouse. However, A-Frame recognizes when it is running on a mobile device and will use the rotational sensors to correctly orient the camera.
A-Frame also provides a button to switch into 'Cardboard Mode'. On a non-mobile device, it will simply full-screen the experience, but on a mobile device, it will split the screen into two stereoscopic displays. The images displayed on each half of the screen are essentially being rendered from two separate cameras in the scene, separated by a distance equal to the average inter-pupillary distance (distance between pupils). When placed in a Google Cardboard spec device, each eye will see one half of the screen, and since each eye sees a slightly different view, the viewer will perceive a 3D effect.
Below is an implementation of quicksort that swaps the elements around if they are out of place, rather than sorting them into left and right piles as above.
const quicksort = (array, start = 0, length = array.length) => {
if (length < 2) { return array; }
const pivotIdx = partition(array, start, length);
const leftLength = pivotIdx - start;
const rightLength = length - (leftLength + 1);
quicksort(array, start, leftLength);
quicksort(array, pivotIdx + 1, rightLength);
return array;
}
const partition = (array, start, length) => {
let pivotIdx = start;
const pivot = array[start];
for (let i = start + 1; i < start + length; i++) {
const val = array[i];
if (val < pivot) {
array[i] = array[pivotIdx + 1];
array[pivotIdx + 1] = pivot;
array[pivotIdx] = val;
pivotIdx += 1;
}
}
return pivotIdx;
}