## 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 = x
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 ;
val it = : 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 = : 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
}
```
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/