Sort: Counting sort

Context

Counting sort is a sort algorithm dedicated to lists having values in a small set. Then, one can create an array of same size and store values (or count) while reading.
Using BrainFuck, all our values are stored between 0 and 255. Therefore, it might be an interesting sort algorithm. Let's implement it.
Initial state

• Memory: 0 0 [array] 0 0 0 0 0 ... where array is a 2 cells block array of nullable integers
• Pointer: just after array
• Input: any

Process

• Generate counter array
• That's a 2 cells block array of nullable integers, of size 256
• Generate the first cell
• Then have 255 in a counter and generate all cells after
• For each integer N from the list
• Access item N in array and increment counter
• Optionally, we can rebuild back the array when sort is completed
• Define current value (initially: 0)
• For each counter C in counter array
• Add current value C times
• Increment current value

Code - try it

generate counter array: 2 cells array with 256 items
->>>>>+<<<<<[->>>>>[>>]+[<<]<<<]

read integers one by one and store into array
go to first integer and loop
<<[<<]>>
[
  remove cell indicator
  -
  move value to end
  >[->[>>]>+<<<[<<]>]
  go to value and move backward
  >[>>]>[-<+>]
  access array cell given by index
  <[->>>[>>]+>>->[-<<+>>]<<<[<<]<]
  increment count for given value
  >>>[>>]>>>+
  move array back to position
  <<<<<[[->>+<<]>[->>+<<]<<<]
  go to next integer
  <<<[<<]>>
]

rebuild array of values
>>>>>
[
  move cell
  -<<+>>>[-<<+>>]<<
  add value N that many times
  [
    -
    go to current value
    <[<<]<
    copy / move to end of array
    [->+>+<<]>[-<<<[<<]>+>[>>]>]
    set cell flag
    <<<[<<]+[>>]
    restore current value copy
    >>[-<<+>>]
    go back to value counter
    >[>>]<
  ]
  increment current value
  <[<<]<+
  >>>[>>]>>
  go to next cell and loop
]

clear counter array
<<<<[->[-]<<<]

Final state

• Memory: 0 0 [sorted array] 0 0 0...
• Cursor: 2 cells after array
• Input: unchanged
• Output: unchanged

Notes

1. Due to our array rebuild, the sort is descending, but this can be easily changed to ascending sort
2. Despite a shorter algorithm, execution is really longer than Quicksort

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.

Sort: Bubble sort

Context

There are multiple ways to sort an array in computer theory. One of them is called Bubble sort.
This algorithm is clearly not the best one, though it's quite easy to implement:

• Consider 2 adjacent cells
• Compare values
• If second is smaller, then swap the 2 values
• Move to next pair of 2 cells (the one that includes the second element of my current pair)
• When reaching end of array, redo the whole loop as long as at least one swap has been made (sort is not over)

The name comes from the behaviour of biggest / smaller elements (according to the sort direction) : they are pushed to the top of the list like bubbles in liquids.

Let's write our own bubble sort implementation

Initial state

• Memory: 0 0 [array] 0 0 0 0 0 0 ... where array is an array of nullable integers (2 cells per item, one set to 1 and second set to the value)
• Cursor: just after array
• Input: any

Process

• Set a loop indicator to 1 and start a loop
• Reset loop indicator
• Go to last two cells
• Move and copy the second cell to the right (leave enough space for comparison)
• Copy first cell value
• Compare first and second value copies
• If second is smaller than first
• Swap the 2 values
• RESET the loop indicator and set to 1. Reset is mandatory, otherwise (simply adding 1) will fail if there are 256 changes (loop indicator will then be 0). Here, instead, let's just have the indicator reset and set to 1
• Move to the next pair if any
• Move array back to its original location
• Go back to loop indicator and loop if needed

Code - try it

set loop indicator and loop
>>>>>>>+[
  reset indicator and go to last 2 cells
  -<<<<<<<<<<<
  while there are 2 cells to compare
  [
    copy / move second cell
    >>->[->+>>>>>+<<<<<<]>>>>>+<<<<[-<+>]
    copy first cell
    <<<[->+>>+<<<]>[-<+>]
    compare 2 values
    >>>+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<<
    [-
      second is smaller : swap
      temporarily move first cell
      <<[->+<]
      move first cell
      >>>>>>>>[-<<<<<<<<+>>>>>>>>]
      reset and set loop indicator
      >[>>]>[-]+<<<[<<]<<<<
      move second value
      [->>>>>>>+<<<<<<<]
      go back to position before if
      >
    ]
    move to last 2 cells and loop
    <<<<<
  ]
  move array back to initial location
  >>>>>>>>>>[[-<<<<<<+>>>>>>]>[-<<<<<<+>>>>>>]>]
  go to loop indicator and loop
  >
]

Final state

• Memory: 0 0 [array] 0 0 0 0 0 0
• Cursor: 6 cells after the array
• Input: unchanged
• Output: unchanged