Sort: Quicksort

Context

After Bubble sort, let's see how to implement another algorithm : Quicksort.
Quicksort is really efficient, its mechanism is:

• Select a pivot cell (any cell from the list is fine, we will pick the last one though it has been proven that's the worst case)
• For each other cell
• If value is greater than pivot: move to set B
• Otherwise, move to set A
• Then, recursively sort A and B, and finally rebuild the concatenation [ sorted A ] + pivot + [ sorted B]

Example: let's sort 4, 5, 3, 1, 2

• Pivot: 2, and we generate one set [1] and one set [4, 5, 3]
• Sort [1] -- done
• Sort [4, 5, 3]: pivot is 3 and generates only one set [4, 5]
• Sort [4, 5]: pivot is 5 and generates set [4]
• Sort [4] -- done
• Merge: [4, 5]
• Merge: [3, 4, 5]
• Merge: [1, 2, 3, 4, 5]

Initial state

• Memory: 0 ... (fifteen times) ... [array length] 0 0 [2 cells array to handle null values] 0 0 ...
• Initial pointer:  just after array
• Input: any

Process

• Note: array length can be either computed (see this post - though it's for 1 cell array only but can be adapted easily), or directly computed while reading input if integers are provided by end-user
• We will define a queue of ranges to process
• Memory will looks like 0 0 ... 0 0 [array] 0 0 0 [queue of ranges to process]
• Range: first item index + range length
• First range: {1, array length}, because we will process the whole array
• Therefore, move array length and store value 1 in the queue
• Pick one range definition from queue
• Split array to isolate range
• Items before range start index are moved to the far left
• Items after range index are moved to the (just a bit less) far left as well until range length is reached
• Items after that are unchanged
• Memory : 0 0 [out of range] 0 0 [range to process] 0 ... 0  [out of range] 0 ... 0 [queue]
• Then
• Select a pivot (last item in range to process)
• Store a copy
• This will be our memory during range processing
  [range to process] 0 0 [processed left] pivot 0 pivot 0 0 0 0 [processed rigth]
• For each other item to process
• Store a copy
• Compare to pivot
• Pivot is greater than value : move value to processed left
• otherwise
• move value to processed right
• move processed left to the left
• move pivot and copy to the left as well
• Note: this allows an in-place processing...
• Count items in processed left and merge with pivor
• Merge the whole array
  [out of range] [ processed left] pivot [processed right] [out of range]
• Compute new range definitions - current range starts at S and has length L
• If processed left's length L' is not null: we need to process this block, defined by a start at S and this particular length L'
• Processed right range definition is given by start at S + L' + 1 and length L - L' - 1
• For both ranges, if length is not null, then enqueue range definitions
• Finally, shift the queue to the left (as first elements have been removed), and loop on new range definition
• Stops when no range definition is available (array is sorted)

Code - try it (generic example) or try it (alphabet sort)

move count and create first range
<<[<<]<[->>>[>>]>>>>+<<<<<<[<<]<]>>>[>>]>>>+

while there is a range to process
[
  copy range start index and split array at this position
  <+>-[-<<<<<[<<]>>[-<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>]>[-<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>]>[>>]>>+>]

  copy range length and split array for this number of items
  >[-<<<<<<[<<]>>[-<<<<<<<<<<<<<<+>>>>>>>>>>>>>>]>[-<<<<<<<<<<<<<<+>>>>>>>>>>>>>>]>[>>]>>>+>]

  go to array isolated range
  <<<<<<[<<]<<<<<<<<<<<<<<

  copy pivot
  ->[->>>+>>+<<<<<]

  go to first element to process
  <<<

  while there is an element to process
  [
    copy element for save and comparison
    ->[->>>[>>]>>>+>>+<<<<<<<[<<]<]>>>[>>]>>>>
    compare copies
    >>+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<+<
    [>-<
      pivot is less than current: move current into the right part
      -<[->>>>>>>+<<<<<<<]>>>>>>+
      move the left part to reuse free space
      <<<<<<<<<<<[<<]>>[[-<<+>>]>[-<<+>>]>]
      move pivot for same reason and copy it
      >>[-<+<+>>]<[->+<]>>
    ]
    >[-
      pivot is greater than current: move current into the left part
      <<[-<<<<<[<<]>+>[>>]>>>]<<<<<[<<]+[>>]
      copy pivot
      >>[->+>+<<]>[-<+>]>>>
    ]
    in all cases current position is 2 cells after second pivot copy
    go to next cell to process
    <<<<<<<<[<<]<<
  ]
  reset pivot copy
  >>>>[>>]>>[-]
  count left part length and merge
  <<<<[
    move
    ->[->>+<<]>+
    increment counter
    >>[>>]>>>>>+<<<<<<<[<<]<<
  ]
  include pivot
  >>>>[>>]+>>[-<+>]
  move left part length outside array
  >>>[->>>>[>>]>>>[>>]>+<<<[<<]<<<[<<]<<]
  rebuild whole array
  move right part of sorted range
  >>>>[>>]<<[->[->>>+<<<]>>+<<<<<]
  move left part of sorted range and pivot
  <<<<<<<[->[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>+<<<<<<<<<<<<]
  move left part outside range
  <<<<<<[->[->>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<]

  compute next range(s) definitions
  got to left part length
  >>>>>>>>>>>>>>>>>>[>>]>
  [
    if not null: add left range definition
    start: same as current start
    length: given by current value

    copy and push start
    >[-<<+>>>>>[>]>+<<[<]<<]<<[->>+<<]
    copy and push length
    >[-<+>>>>>[>]>>+<<<[<]<<<]
    add new range on queue
    >>>>[>]>[[-<+>]>]<<[<]<<<
    move left part length to the left to break loop (which is actually an if)
  ]
  compute second possible range start (current range start increased by left range length and pivot)
  compute as well second possible range length (current range length decreased by left range length and pivot)
  <[->>+>-<<<]>>+>-
  [
    if length is not null: move to queue
    <[->>>[>]>+<<[<]<<]
    >[->>[>]>>+<<<[<]<]
    >>[>]>[[-<+>]>]<<[<]<
  ]
  reset second range length if needed
  <[-]
  shift the queue
  >>>[[-<<+>>]>]
  go to next range definition in queue
  <<<[<]>
]

Final state

• Memory: [eighteen zeros] [sorted array] 0 0 0 0
• Cursor: 4 cells after array
• Input: unchanged
• Output: unchanged

Note: one can check that this code, even if more complex, is really faster, even in brainfuck, than the bubble sort implementation.

Recursion vs iteration: compute factorial

Context

There are two ways to deal with loops in computer science: the recursive way and the iterative way.

• Recursion: a function that contains calls to itself, creating a loop through nested calls
• Iteration: do something until a condition is met

Both have pros and cons.

Using recursion, it's generally easier to prove algorithm validity by induction: if you can prove that your result is correct for smallest input possible, and that having a valid result for an input N implies a valid result for N+1, then your algorithm is valid for any input.

But recursion also implies to carefully watch at the memory stack: each recursive call uses memory, and you may reach a 'stack overflow' after too many recursive calls...

Using iterations, you can do something a given number of times, not necessarily using more memory on each loop. Validity can be proven as well, but using an invariant that might be complex to find.

In BrainFuck however, there are no functions, so how can we use recursive calls?

It actually requires to understand one of the key points of recursion: what happens when you have something like

function F(n)
  do something
  F(n')
  do something

Calling function F (any function actually) will

• Push on stack some details about the returning point
• Push also function parameters
• Then execute code

In BrainFuck, we can easily do something similar.

Let's implement the factorial function, denoted by n! = product of all integers from 1 to n.

• The iterative definition of this function is n! = 1 * 2 * 3 ... * n
• The recursive definition is n! = n * (n-1)!, with 0! = 1

Note: as factorial grows faster than any polynomial or exponential function, we may reach integer limit pretty quickly. Actually, BrainFuck uses memory cells valued from 0 to 255, modulo 256, so:

• 5! is the biggest integer we may have (120)
• 6!, 7!, 8!, 9! will be computed modulo 256
• 10! is divisible by 256, so any n! mod 256 with n ≥ 10 will be 0

Therefore, there is no need to read complex integers in our algorithms. A single digit is enough

Initial state

• Memory: empty
• Cursor: first cell
• Input: one char

Process

• Read character, convert to integer (-48). This would be n
• Iterative way
• Set a cell to 1 (this would be our result)
• While n is not null
• Decrease n
• Increase the cell besides (let's call it j)
• Multiply our result by j
• Loop invariant: result equals j! and n+j = initial value of n
• When n is null, then j = initial n, and result = initial n!
• Recursive way
• While current cell is not null
• Copy value 2 cells on the right
• Decrease copy by 1, and stay on this copy
• Move to left, set result to 1, move to left
• While current cell is not null
• multiply this value with the next cell's one
• store result on the previous cell
• move 2 cells on the left compared to the original position

Note: the recursive algorithm is a bit harder to understand. We will

• Generate a memory that looks like n 0 n-1 0 n-2 0 ... 2 0 1 0 0
• Then, set the red cell to 1 : ... 2 0 1 1 0
• Multiply 1 by 1 and store the result after 2 : ... 3 0 2 1 0 0 0
• Multiply 2 by 1 and store the result after 3 : ... 4 0 3 2 0 0 0 0 0
• Multiply 3 by 2, and so on...

Code (iterative version) - try it

read n
,>++++++++[-<------>]
set result to 1
>>>+<<<<
while n is not null
[
  decrease n and increase j by one
  ->+
  copy current value of j
  [->+>+<<]>[-<+>]>
  multiply current result by j
  -[->[->+>+<<]>[-<+>]<<]>>>[-<<+>>]<<<
  go back to n and loop
<<<]

Code (recursive version) - try it

read n (leave some free space to stop the final loop)
>>,>++++++++[-<------>]
generate all integers from n to 0 separated by 0
<[[->+>+<<]>[-<+>]>-]
set result to 1 and move to integer '1'
<+<
While current integer is not null
[
  multiply result by current integer
  [->[->+>+<<]>[-<+>]<<]
  store result at its new location (and reset temporary cells)
  >>>[-<<<<+>>>>]<<[-]<
  go to previous integer in the stack
<<]

Final state 

• Memory : 
• Iterative method: 0 n 0 0 n!
• Recursive method: 0 n! 0 0 
• Pointer: first cell (in both cases)
• Input: one character read
• Output: unchanged