32
\$\begingroup\$

As discussed in the Lounge room on Stack Overflow:

if you can't implement the Quicksort algorithm given en.wikipedia.org/wiki/Quicksort in any language you have minimal knowledge of, you might want to consider a different profession. @sbi

but SBI also noted that maybe BrainF*** was an exception.

So, here's the puzzle/challenge: implement QuickSort in BrainF***. The implementation must

  • be interpreted by this and/or by the interpreter(s) here (for large scripts)
  • implement the algorithm as described on Wikipedia - if possible as an in-place sort
  • sort the following list of integers: [0,4,6,4,2,3,9,2,3,6,5,3] and print the result
\$\endgroup\$

closed as off-topic by Martin Ender Dec 1 '17 at 15:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Martin Ender
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Searching around a bit I'm able to find one implementation, but it's 6kB (and compiled from Haskell). \$\endgroup\$ – Peter Taylor May 3 '11 at 23:02
  • \$\begingroup\$ @Peter actually the brainfuck implementation is 474.2 K inside the archive - which is a bit bigger than I expected (and too big for the on-line interpreter). Maybe I should change the target interpreter.. (but I would love to see something hand-written) \$\endgroup\$ – Ronald May 4 '11 at 0:01
  • 22
    \$\begingroup\$ I bet I could do bubble sort instead and nobody looking at the code would know the difference... \$\endgroup\$ – Peter Olson May 4 '11 at 16:37
  • 1
    \$\begingroup\$ @Keith the idea is to really implement QuickSort, not just any sort that'll work... :-) \$\endgroup\$ – Ronald May 4 '11 at 20:55
  • 1
    \$\begingroup\$ @Peter Of The Corn: We would discover a bubble-sort by the bad performance. \$\endgroup\$ – user unknown Jul 13 '11 at 16:57
55
\$\begingroup\$

BrainF* (697 bytes)

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

Below is an annotated version. In order to keep track of what was supposed to be happening while developing it, I used a comment notation that looks like this: |a|b=0|c=A0|@d|A0|A1|```|

|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)

The memory is laid out with a left-growing stack of partitions to process on the left, a scratch space in the center, and the array being sorted to the right. Array indexing is handled by moving a "data bus" containing the index and working space through the array. So for instance a 3-wide bus of |i|data|0|A0|A1|A2, will become |A0|i-1|data|0|A1|A2 after shifting by one. The partitioning is performed by keeping the bus between the high and low elements.
Here's the full version:

Get input
>>>>>>>> ,[>,]                      |A0|A1|```|An|@0|
Count items
<[ [>>>+<<<-]>[<+>-]<+ <]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
>[<<<<<<<<+>>>>>>>>-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
<<<<<<<<[
  Copy K1 to a&c via Z
  [>>+>+>>+<<<<<-]>>[<<+>>-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&d via Z
  <[>+>>+>>+<<<<<-]>[<+>-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  >>>>[-<->]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +<[>- >+<<-[>>-<<[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  >[<+>-]>[<<+>>-]<+<      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [->-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    <<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  >>>>]>[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    <<+[ -[>+<-]<-[>+<-]>>>>>>>>      (dec J as we move)
      [<<<<<<<<+>>>>>>>>-]<<<<<< ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    <<[>>+<<-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    >[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      >[>+>>+<<<-]>[<+>-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      >>>>>>[<+<+>>-]<[>+<-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g 
      <<<[ >+>[<-]<[<]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g 
        >>[<<+>[-]+>-]>-<<-]
      set g to 1; if d: set f 
      >>[-]+<<< [->>+<<]
      If Aq LT Ap move Aq across Bus
      >>[->- <<<<<[>+<-] <[>+<-] >>>>>>>>
        [<<<<<<<<+>>>>>>>>-] <<]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq                
      >[[-] <<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      >>>>>[-
        & While J shuttle right
        [>>[<<<+>>>-]<[>+<-]<-[>+<-]>] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        <<[ [>>+<<-] < ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]>]
    Either bus moved or last element swapped; reduce J in either case
    <<<<<<-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    >[>>>>>>+<<<<<<-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    <<[ [>>>>>>>+<<<<<<<-]>[<+>-]<+ <]     
    <[ [>>>>>>>>+<<<<<<<<-]>>[<+>-]<+ <<] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    >+>[<-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      <<[>+<-] <[<]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p| 
      shift left until return to 0 at K0;
      >[ [<+>-] >]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      >>>[<<<<+>>>>-]<<[<+>-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty) 
    >>]<[- <<+>>]              
  >>>]  End if !empty
<<<<<<] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
>>>>>>>>>>>[.>]
\$\endgroup\$
  • \$\begingroup\$ I was working on a similar solution but couldn't quite get it working. Awesome idea to do the partitioning that way. I was pulling out one element at a time and replacing it, and it got quite cumbersome quite quickly. I was also 1.5k into it, so you destroyed me on efficiency too. \$\endgroup\$ – captncraig Jan 20 '12 at 17:01
  • 1
    \$\begingroup\$ Everything in BF gets cumbersome quite quickly :) Even seemingly simple things like how to do an efficient if (i<j) {} else {} took several tries to get right. And the edge cases are killers. I don't know how many times I thought "just this one little thing left..." and then discovered a test case which caused another several hours work to handle. I think I can reduce it by a few dozen characters, but I'm not sure I want to put in the effort. \$\endgroup\$ – AShelly Jan 20 '12 at 19:18
  • \$\begingroup\$ One word: wow! I honestly didn't think it was humanly possible. I'm going to run a few inputs through it just to see how it works :-) \$\endgroup\$ – Ronald Jan 23 '12 at 0:05
  • \$\begingroup\$ Epic! Just epic! \$\endgroup\$ – vsz Jun 29 '12 at 18:04
  • \$\begingroup\$ the only thing to say is "holy f*ck!" \$\endgroup\$ – Math chiller Oct 1 '13 at 23:52
11
\$\begingroup\$

brainfuck (178 bytes)

Even if brainfuck is cumbersome, it helps to work with the grain of the language. Ask yourself "Do I have to store this value explicitly in a cell?" You can often gain speed and concision by doing something more subtle. And when the value is an array index (or an arbitrary natural number), it may not fit in a cell. Of course, you could just accept that as a limit of your program. But designing your program to handle large values will often make it better in other ways.

As usual, my first working version was twice as long as it needed to be—392 bytes. Numerous modifications and two or three major rewrites produced this comparatively graceful 178-byte version. (Though amusingly a linear-time sort is only 40 bytes.)

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

The input values are spaced every three cells: for every (V)alue cell, there is a (L)abel cell (used for navigation) and one more cell for (S)cratch space. The overall layout of the array is

0 1 0 0 0 S V L S V L ... S V L 0 0 0 0 0 0 ...

Initially all the L cells are set to 1, to mark portions of the array that still need sorting. When we're done partitioning a subarray, we divide it into smaller subarrays by setting its pivot's L cell to 0, then locate the rightmost L cell that's still 1 and partition that subarray next. Oddly, this is all the bookkeeping we need to properly handle the recursive processing of subarrays. When all L cells have been zeroed, the whole array is sorted.

To partition a subarray, we pull its rightmost value into an S cell to act as pivot, and bring it (and the corresponding empty V cell) left, comparing it to each other value in the subarray and swapping as needed. At the end the pivot gets swapped back in, using the same swap code (which saves 50 bytes or so). During partitioning, two extra L cells are kept set to 0, to mark the two cells that may need to be swapped with each other; at the end of partitioning, the left 0 will fuse with the 0 to the left of the subarray, and the right 0 will end up marking its pivot. This process also leaves an extra 1 in the L cell to the right of the subarray; the main loop begins and ends at this cell.

>+>>>>>,[>+>>,]>+[                      set up; for each subarray:
    --[+<<<-]<[                         find the subarray; if it exists:
        [<+>-]<[                        S=pivot; while pivot is in S:
            <[                          if not at end of subarray
                ->[<<<+>>>>+<-]         move pivot left (and copy it) 
                <<[>>+>[->]<<[<]<-]>    move value to S and compare with pivot
            ]>>>+<[[-]<[>+<-]<]>[       if pivot greater then set V=S; else:
                [>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]     swap smaller value into V
                <<[<<<]>[>>[>>>]<+<<[<<<]>-]        swap S into its place
            ]+<<<                       end else and set S=1 for return path
        ]                               subarray done (pivot was swapped in)
    ]+[->>>]>>                          end "if subarray exists"; go to right
]>[brainfuck.org>>>]                    done sorting whole array; output it
\$\endgroup\$
  • 1
    \$\begingroup\$ Awesome. It's so much cleaner when you work with BF's idioms, instead of trying to force it to act like a procedural language, like I did. \$\endgroup\$ – AShelly Sep 14 '17 at 17:32
  • \$\begingroup\$ It is; but version 4 at 392 bytes was idiomatic brainfuck too. This is version 39 or so. :) \$\endgroup\$ – Daniel Cristofani Sep 17 '17 at 2:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.