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.

Pages: 1 2

10 Responses to “Friday Fun”

  1. Zack said

    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

    for i = 2:n
        if (ascending & (x[i] >= y[c])) || (!ascending & (x[i] <= y[c]))
            c += 1
            y[c] = x[i]
        end
    end
    
    return y[1:c]
    

    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!

  2. chaw said

    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:

    ((0 1 2 3 4 5 6 7 8 9) (0) (4 6))
    

  3. Daniel said

    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:

    [4, 6]
    
  4. Daniel said

    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:

    $ ./a.out 4 2 3 6 1 5
    4 6
    
  5. mcmillhj said

    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
    *)
    
  6. ibiwan said

    Sounds like DropSort — my implementation in python is linked from the descriptive page below:
    http://www.dangermouse.net/esoteric/dropsort.html

  7. Zack said

    @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!

  8. Bill Wood said

    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

  9. Bill Wood said

    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"]));
    
  10. ibiwan said

    @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/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: