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
>>>>>>>>>>>[.>]
Searching around a bit I'm able to find one implementation, but it's 6kB (and compiled from Haskell).
– Peter Taylor – 2011-05-03T23:02:41.237@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) – Ronald – 2011-05-04T00:01:56.703
Actually, I got an error on that one: an underflow at byte 484109 (using the bcci interpreter) – Ronald – 2011-05-04T00:12:41.820
@Ronald, yes, oops. Looked at the wrong component of the output of
wc
. – Peter Taylor – 2011-05-04T06:03:20.353Quick question: can I assume that all the integers are only one digit? It would make things so much simpler. And if not, can I at least assume that they can be stored in a single byte (i.e. in the interval [0,255])? Can the number be negative? – Peter Olson – 2011-05-04T15:39:15.533
Also, are we allowed to use procedural brainf***? – Peter Olson – 2011-05-04T15:48:05.290
@Peter Yes, integers will be single-digit. No procedural BrainFuck though. – Ronald – 2011-05-04T16:31:03.173
22I bet I could do bubble sort instead and nobody looking at the code would know the difference... – Peter Olson – 2011-05-04T16:37:29.090
something like
– Ronald – 2011-05-04T16:58:33.170>>,[>>,]<<[[-<+<]>[>[>>]<[.[-]<[[>>+<<-]<]>>]>]<<]
(by Daniel B Cristofani) perhaps?If the elements are only 0-9, counting sort would work pretty well also... – Keith Randall – 2011-05-04T20:33:47.537
1@Keith the idea is to really implement QuickSort, not just any sort that'll work... :-) – Ronald – 2011-05-04T20:55:41.567
1@Peter Of The Corn: We would discover a bubble-sort by the bad performance. – user unknown – 2011-07-13T16:57:54.707
I can try to code a merge sort, but since the quick sort requires recursion, coding a quick sort is impossible for me. (I admire every brainfucker who implemented functions and recursions in BF - like C2BF) – JiminP – 2011-10-09T07:54:18.180
I'm gonna do this. By hand. I have a data model that I think will work, but holy cow it may take a miracle. – captncraig – 2011-12-15T23:57:55.640