Exercise on Runtime data: Quicksort

Here is the quicksort program.  Draw the "stack frame" (in other name, "activation record") when quicksort() calls itself three times. Assuming you don't have to trace into "partition" function.

Inside the activation record contains: local variables, frame pointer, stack pointer.  Show values of all of them in each AR.

// quicksort

var N = 20, a

to inita()
  for i 0 N-1
    a[i] = N - i

to swap(i j)
  t = a[i]
  a[i] = a[j]
  a[j] = t

to partition(p r)
  x = a[p]
  i = p - 1
  j = r + 1
  flag = 1
  while flag
    j = j - 1
    while a[j] > x
      j = j - 1
    i = i + 1
    while a[i] < x
      i = i + 1
    if (i < j) swap i j else flag = 0
  return j

to quicksort(p r)
  if p < r
    q = partition p r
    quicksort p q
    quicksort q+1 r

to main()
  a = array N
  inita
  quicksort 0 (N - 1)


//  end