Sorting algorithms/Shell sort/Whitespace
This solution was tested and found to work correctly with the canonical Haskell interpreter, this Ruby version, and Pavel Shub's glorious 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 EOF 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 Ideone.
<lang Whitespace>
</lang>
While 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>