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: 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

Null values in arrays

Context

As mentioned in this previous post, array implementation induces a limitation: elements cannot be null. Let's now see how to deal with zeros.
To access an element in an array, we need to go through all elements, so use a loop. And loops stop when value reached is null. Therefore, our current array structure doesn't fit.

However, it's still possible to have arrays with 2 memory cells per element: first that contains a non-zero value (any value, but let's say 1), and second that contains the actual element value.
Then, to access elements in the array, we need to iterate on blocks of 2 cells.

Code sample

>>+ first separator

>>, read char

[

  >++++[-<----------->]+< comma check

  [---- convert to digit value

    >++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>] multiply current by ten and add new digit

  ]>[ comma case

    <+>->> add cell with 1 and start next number

  ]<,]

<<[<<]>> go back to array last element (first cell) then back to the array beginning

This block of code read comma-separated decimal numbers, including 0, and store them in memory cells separated by cells containing 1.

The last line shows how to move back to the array first element.