TRAKLA2 - Quicksort

Quicksort

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Use quicksort to sort the table below. The parameters are on top of the call stack, denote the boundaries of the currently active area. The parameters of the initial quicksort function call have been placed in the stack as a starting point. In each recursive call to quicksort, the user first has to partition the area by swapping keys (dragging by mouse) in respect to the pivot. After the partitioning, the pivot is swapped into its new place. Then the user can select the subarea to the left from the pivot (by clicking the indices of the area bounds) and then call the quicksort-function (by clicking the call button) to place the parameters in the call stack. This procedure is then applied recursively. When we return from a function call (by clicking the return button) to the left subarea, a call for the right subarea is performed. If the subarea is of size 3 or less, it can be sorted using any way you wish. For more specific details, please consult the pseudo code provided below Some additional problems.
Quicksort Partition Coloring cues quicksort(array:Array, left:integer, right:integer) if \|left-right\| < 3 sort by any method else split = partition(array,left,right) if (split-1)-left > 0 quicksort(array, left, split-1) if right-(split+1) > 0 quicksort(array, split+1, right) endif end partition(array:Array, left:integer, right:integer) : integer leftCursor = left %Pivot is hidden in the right rightCursor = right - 1 pivotValue = array[right] do while (array(leftCursor) < pivotValue) leftCursor = leftCursor + 1 while (rightCursor >= 0 AND array(rightCursor) >= pivotValue) rightCursor = rightCursor - 1 if (leftCursor < rightCursor) swap array elements at leftCursor, rightCursor while (leftCursor < rightCursor) swap array elements at leftCursor, right return from function with value:leftCursor The pivot is colored orange to make it more visible. Inactive (sorted) items are colored gray An area to be sorted that has a size of 3 or less items is colored yellow.