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).
(import (scheme base) (scheme write) (only (srfi 1) iota)) (define (stalin-sort items item<?) (if (null? items) items (let ((survivors (list (car items)))) (let loop ((unseen (cdr items)) (current survivors)) (cond ((null? unseen) survivors) ((item<? (car unseen) (car current)) (loop (cdr unseen) current)) (else (set-cdr! current (list (car unseen))) (loop (cdr unseen) (cdr current)))))))) (display (map stalin-sort (list (iota 10) (iota 10) '(4 2 3 6 1 5)) (list < > <))) (newline)Output:
Here’s a solution in Python.
def sort(l): output = [] for x in l: if not output or x >= output[-1]: output.append(x) return output l = [4, 2, 3, 6, 1, 5] print(sort(l))Output:
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> // modifies array in-place and returns new length int sort(int* array, int n) { if (n == 0) return 0; int pos = 0; for (int i = 1; i < n; ++i) { if (array[i] < array[pos]) continue; array[++pos] = array[i]; } return pos + 1; } void print_array(int* array, int n) { for (int i = 0; i < n; ++i) { if (i > 0) printf(" "); printf("%d", array[i]); } printf("\n"); } int main(int argc, char* argv[]) { int n = argc - 1; int* array = malloc(sizeof(int) * n); for (int i = 0; i < n; ++i) { array[i] = atoi(argv[i+1]); } n = sort(array, n); print_array(array, n); free(array); return EXIT_SUCCESS; }Example:
SML solution (only works for int list :\ though):
fun stalin_sort [] = [] | stalin_sort [x] = [x] | stalin_sort (x::y::zs) = if x <= y then x :: stalin_sort (y::zs) else stalin_sort (y::zs) (* ➜ poly --use stalin_sort.sml Poly/ML 5.8 Release val stalin_sort = fn: int list -> int list > stalin_sort []; val it = []: int list > stalin_sort [1]; val it = [1]: int list > stalin_sort [1,2,3,4,5]; val it = [1, 2, 3, 4, 5]: int list > stalin_sort [5,4,3,2,1]; val it = [1]: int list *)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:
fn main() { let x = vec!(1,2,3,2,5,8,4,9); println!("{:?}", stalin_sort(x)); let x = vec!('a','b','c','b','e','g','d','x'); println!("{:?}", stalin_sort(x)); } fn stalin_sort<T: PartialOrd>(x: Vec<T>) -> Vec<T> { let mut y = vec!(); for v in x { if y.len() == 0 || &v >= y.last().unwrap() { y.push(v); } } y }Rust Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6446b7738f09a41fdc3d84d35aebd196
Reason version
/* Author Bill Wood */ let rec stalinSort = fun | [] => [] | [x] => [x] | [x, y, ...tail] => x <= y ? [x, ...stalinSort([y, ...tail])] : stalinSort([x, ...tail]); Js.log(stalinSort([1,2,3,2,5,8,4,9])); Js.log(stalinSort(["a","b","c","b","e","g","d","x"])); Js.log(stalinSort([ "Fully Automated Luxury Space Communism", "Socialism", "Capitalism", "Communism"]));@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/