Anonymous user
Sorting algorithms/Shell sort/Whitespace: Difference between revisions
Sorting algorithms/Shell sort/Whitespace (view source)
Revision as of 09:10, 10 March 2013
, 11 years agoNix some fluff, reveal the trick
(Add Whitespace implementation) |
(Nix some fluff, reveal the trick) |
||
Line 1:
This solution was tested and found to work correctly with the canonical [http://compsoc.dur.ac.uk/whitespace/download.php Haskell interpreter], [https://github.com/hostilefork/whitespacers/tree/master/ruby this Ruby version], and Pavel Shub's glorious [http://pavelshub.com/blog/2010/10/wspace/ C++ implementation]. Most others either failed to run even the simplest of programs, were Windows-only, or else required tiresome setup.
It was observed early on that hard-coding the values to be sorted might rouse suspicion as to whether such an inscrutable program were really doing any sorting; thus it was decided that input would be provided at runtime. This led to the unfortunate discovery that not all of the aforementioned interpreters handle <tt>EOF</tt> in the same way; Haskell and Ruby error out where C++ returns a convenient -1. In the interest of compatibility, the program reads values until a literal -1 is provided; all other negative numbers are permissible and will be sorted appropriately
A demonstration of the program capable of receiving further test input is available on [http://ideone.com/zVfzfy Ideone]
<lang Whitespace>
Line 87:
</lang>
While [http://i.imgur.com/8LhJoDG.png semantic highlighting] makes the code slightly less opaque (read: transparent), it's much easier to read the pseudo-Assembly from which it was generated.
<lang asm>; This is used as the index into the heap while reading, after which it
; holds the number of elements to sort. We shall henceforth call him n.
push 0
0:
dup ; Storing input is destructive [n n]
dup ; so we dup the index twice. [n n n]
inum ; Read a number into the heap. [n n]
load ; Get it onto the stack. [n #]
push 1 ; Detect when -1 is supplied as input [n # 1]
add ; to simulate EOF [n #+1]
jz 1 ; and stop reading. [n]
push 1 ; Otherwise, [n 1]
add ; increment [n+=1]
jump 0 ; and go again. [n]
1:
dup ; Initialize h (outermost loop) to n. [n h]
push 0 ; Buffer to enable clean i < n exit. [n h 0]
2:
pop ; Drop that 0 or an extraneous i. [n h]
push 2 ; Constant 2-gap because reasons. [n h 2]
div ; h /= 2 [n h/=2]
dup ; Branch checks eat stack. [n h h]
jz 6 ; If h is 0, we're all sorted. [n h]
dup ; Initialize i (middle loop) to h. [n h i]
3:
dup ; We need a copy of i to play with. [n h i i]
copy 3 ; Get n for i < n check. [n h i i n]
sub ; i is never greater than n, but [n h i i-n]
jz 2 ; exit the loop if they're equal. [n h i]
dup ; Loading eats stack and we need i. [n h i i]
load ; k = a[i] [n h i k]
copy 1 ; j = i [n h i k j]
4:
dup ; Copy j the first of many times. [n h i k j j]
copy 4 ; Grab h from way down there. [n h i k j j h]
sub ; Check first condition. [n h i k j j-h]
jn 5 ; j >= h failed, exit loop. [n h i k j]
dup ; Retrieve j and h again; dup would [n h i k j j]
copy 4 ; have complicated the stack for 5. [n h i k j j h]
sub ; Prepare for retrieval, then [n h i k j j-h]
load ; grab a[j - h], which we'll call x. [n h i k j x]
copy 2 ; Get k to check k < x. [n h i k j x k]
push 1 ; <, not <= so handle the 0 case [n h i k j x k+1]
add ; by incrementing k [n h i k j x k+=1]
sub ; before subtracting it from x. [n h i k j x-k]
jn 5 ; k < x failed, exit loop. [n h i k j]
dup ; Another j. [n h i k j j]
dup ; Guess which variable we need. [n h i k j j j]
copy 5 ; Grab a copy of h [n h i k j j j h]
sub ; to subtract it from j [n h i k j j j-h]
load ; to retrive a[j - h] [n h i k j j x]
store ; and swap it into j, a[j] = a[j - h] [n h i k j]
copy 3 ; Grab one more h [n h i k j h]
sub ; to decrement the loop variable [n h i k j-=h]
jump 4 ; and go again.
5:
swap ; Prepare for second swap. [n h i j k]
store ; a[j] = k [n h i]
push 1 ; Do the middle loop's afterthought. [n h i 1]
add ; i++ [n h i+=1]
jump 3
6:
pop ; It's just you now, n. [n]
push 0 ; A counter so we can print ascending. [n c]
7:
dup ; Need to load and then increment. [n c c]
load ; Grab the next sorted element. [n c a[c]]
onum ; Display it. [n c]
push 10 ; Legibly, of course. [n c 10]
ochr ; With a newline. [n c]
push 1 ; Increment [n c 1]
add ; the counter. [n c+=1]
dup ; We might need it for another run. [n c c]
copy 2 ; Load the total [n c c n]
sub ; and see if we're finished. [n c c-n]
jn 7 ; Negative means go again. [n c]
pop ; Otherwise, exit [n]
pop ; nice and clean. []
exit</lang>
| |||