Friday Fun
August 2, 2019
I wish I thought of this:
I came up with a single pass O(n) sort algorithm I call StalinSort. You iterate down the list of elements checking if they’re in order. Any element which is out of order is eliminated. At the end you have a sorted list.
Your task is to implement StalinSort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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/