Sorting Algorithmn Visualization

160 Project Report - Gerardo Perez

Overview

Here we have a visualization of QuickSort in OpenGL. I completed a big portion of what I wanted to do initially. The pseudocode below is actually quite simple compared to what I had to write.

		//finishes when left == right
		Quicksort(Array, left, right)
			if(left < right)
			pivot = partition(A, left, right)
			Quicksort(Array, left, pivot - 1) //Left Side
			Quicksort(Array, pivot + 1, right) //Right Side

		//In my implementation, pivot is always rightmost element.
		Partition(Array, left, right)
			pivotValue = Array.at(right)
			storeIndex = left
			for i = left to right - 1
				if A.at(i) <= pivotValue
					swap A.at(storeIndex) with A.at(i)
					storeIndex++
			//Here the pivot is always swapped to this position
			swap Array.at(storeIndex) with Array.at(right) 
			return storeIndex;
		

Some Images

The blocks that aren't transparent are the ones that are currently being partitioned. The block with the arrow points at storeIndex in my visualization. The purple block at the bottom points at i.

Usage

1. Space Pauses and Resumes the Animation
2. S steps through the animation. This is partially working, up until when the subarray is sorted. Then you have to pause and unpause a few times to get it started again.
3. Hold the right mouse button and drag to zoom out.