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.

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: