Friday Fun
August 2, 2019
This is easy:
(define (stalin-sort lt? xs) (let loop ((xs (cdr xs)) (zs (list (car xs)))) (if (null? xs) (reverse zs) (if (lt? (car zs) (car xs)) (loop (cdr xs) (cons (car xs) zs)) (loop (cdr xs) zs)))))
And here’s an example:
> (stalin-sort < '(4 2 3 6 1 5)) (4 6)
You can run the program at https://ideone.com/kFjs1o.
Nifty little drill! Here is my take on it using Julia 1.1:
function stalin(x::Array{Int64, 1}, ascending::Bool = true)
n = length(x)
y = Array{Int64}(undef, n)
y[1] = x[1]
c = 1
end
Note that I’ve included the order of the sorting as a parameter, since if a list is ordered in a descending manner, it’s still sorted. Have a nice weekend!
The algorithm description mentions “single pass” so I wrote the
following after writing a simpler, but two-pass solution using fold
and reverse (that is similar to the 2-pass solution by
@programmingpraxis).
Output:
Here’s a solution in Python.
Output:
Here’s a solution in C.
Example:
SML solution (only works for int list :\ though):
Sounds like DropSort — my implementation in python is linked from the descriptive page below:
http://www.dangermouse.net/esoteric/dropsort.html
@ibiwan, it’s fascinating to see that there is an actual practical application of this algorithm. I sincerely thought it was just a drill for honing one’s programming skills. Cheers!
Rust generic version:
Rust Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6446b7738f09a41fdc3d84d35aebd196
Reason version
@zack oh definitely not — the page I linked is a list of ridiculous and esoteric programming languages and algorithms. the original description was as tongue-in-cheek as stalinsort, and my implementation was just going along with the joke to make it actually work on real data: http://www.dangermouse.net/esoteric/