BrainFuck part 9 - Sort arrays with Bubble and QuickSort

Bubble sort

The bubble sort is clearly not know as the best sort algorithm, though it's easy to implement.

Compare two adjacent cells and swap the 2 values if first is greater than second, then move the bubble along the array. This way, smaller values will be moved up, like bubbles on water.

Let's start

• Memory: 0 array 0 0 0
• Cursor: after last array cell
• Input: any

Process

• note : we will go through the array from end to beginning, to make sure there is always enough space
• Set a continue loop flag to 1
• Memory : 0 0 array1 0 0 0 0 0 array2 0 loopFlag
• While loop flag is not null
  • Reset loop flag
  • Go to the end of array1
  • While there are 2 cells
    • Copy them
    • Compare copies
    • If 1st > 2nd
      • moves 1st to beginning of array2
      • set loopFlag to 1 (reset, then set to 1)
    • otherwise move 2nd
  • move array2 back after array1
• loop if needed

Code

>>>>>>+                       set loop flag
[-                            loop: reset flag
  <<[<]<<<<<                  go to end of array 1
  <[                          while there are at least 2 cells
    [[->>>>+<<<<]>]           move the 2 cells
    >>[[-<<+<<+>>>>]>]        copy and move back
    <<<[->+<]<[->+<]>>[-<<    swap the 2 values and then 
    +>>]+<<[->[->]>[<<[-]>>-    compare them 
    >>]<<+<<]>[[-]<+>]>-<+<    ** part 2 **
    [->-<                     2nd smaller than 1st: reset else flag
      <<[->>>>>>+<<<<<<]      move 1st value at beginning of array 2
      >[-<+>]                 and move 2nd at end of array 1
      >>>>>[>]>[-]+           set loop flag to 1
    <<[<]<<<]>[-              else 1st smaller then
      <<[->>>>>+<<<<<]        move 2nd value at beginning of array 2
    >>]                       end if / else
  <<<<]                       loop on new pair
  >>>>>>>[[-<<<<<+>>>>>]>]    move array2 back
>]                            loop if flag is set
<<<<<<                        go to original position one cell after array

Minified version

>>>>>>+[-<<[<]<<<<<<[[[->>>>+<<<<]>]>>[[-<<+<<+>>>>]>]<<<[->+<]<[->+<]>>[-<<+>>]
+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<+<[->-<<<[->>>>>>+<<<<<<]>[-<+>]>>>>>[>
]>[-]+<<[<]<<<]>[-<<[->>>>>+<<<<<]>>]<<<<]>>>>>>>[[-<<<<<+>>>>>]>]>]<<<<<<

Final state

• Memory: 0 sorted array 0 0 0
• Cursor: after last array cell
• Input: unchanged
• Output: unchanged

Test program

This program reads chars from the input, then sort and print them.

>,[>,]
>>>>>>+[-<<[<]<<<<<<[[[->>>>+<<<<]>]>>[[-<<+<<+>>>>]>]<<<[->+<]<[->+<]>>[-<<+>>]
+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<+<[->-<<<[->>>>>>+<<<<<<]>[-<+>]>>>>>[>
]>[-]+<<[<]<<<]>[-<<[->>>>>+<<<<<]>>]<<<<]>>>>>>>[[-<<<<<+>>>>>]>]>]<<<<<<
<[<]>[.>]