## 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 = 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/