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.