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(array:Array, left:integer, 
                right:integer)

  if |left-right| < 3
    sort by any method
  else
    split = partition(array, left, right)

    quicksort(array, left, split-1)
    quicksort(array, split+1, right)
  endif
end
partition(array:Array, left:integer, 
               right:integer) : integer

  leftCursor  = left
  rightCursor = right - 1 %Pivot is hidden in the right
  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.