Help us understand the problem. What is going on with this article?

計算量O(n)で噂のスターリンソートを実装してみた

寝る前にTwitterを見てたらTLにこんなツイートが↓

寝る前に笑わせんなよ寝れねぇじゃねぇか!!ということで実装してみることに

Qiitaには既に先駆者様がいたようですが、自分Haskell読めないです。。。ん~~どう実装したらいいんだろ🤔とりあえず粛清しながらソートすればいいかソートされてない要素を無視するソートにしとけばいいか、という感じの安直な実装したので間違ったソートなら指摘してくださいm(__)m

CSharp

C#erなのでまずはC#から

Program.cs
using System;
using System.Collections.Generic;

#nullable enable
namespace CSharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello Stalin!");
            WriteStalinSort(new[] { 4 });
            WriteStalinSort(new[] { 6, 2, 5, 7, 3, 8, 8, 4 });
            WriteStalinSort(new[] { 5, 3, 7, 8, 9, 5, 3, 5, 7 });
            /**
             * Hello Stalin!
             * Input: 4
             * StalinBy: 4
             * StalinByDescending: 4
             * Input: 6, 2, 5, 7, 3, 8, 8, 4
             * StalinBy: 6, 7, 8, 8
             * StalinByDescending: 6, 2
             * Input: 5, 3, 7, 8, 9, 5, 3, 5, 7
             * StalinBy: 5, 7, 8, 9
             * StalinByDescending: 5, 3, 3
             */
        }

        public static void WriteStalinSort(int[] source)
        {
            Console.WriteLine($"Input: {string.Join(", ", source)}");
            Console.WriteLine($"StalinBy: {string.Join(", ", source.StalinBy(x => x))}");
            Console.WriteLine($"StalinByDescending: {string.Join(", ", source.StalinByDescending(x => x))}");
        }
    }

    public static class StalinSort
    {
        public static IReadOnlyList<TSource> StalinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return source.StalinBy(keySelector, Comparer<TKey>.Default);
        }

        public static IReadOnlyList<TSource> StalinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            return stalinSort(source, keySelector, comparer, false);
        }

        public static IReadOnlyList<TSource> StalinByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return source.StalinByDescending(keySelector, Comparer<TKey>.Default);
        }

        public static IReadOnlyList<TSource> StalinByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            return stalinSort(source, keySelector, comparer, true);
        }

        private static IReadOnlyList<TSource> stalinSort<TSource, TKey>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
        {
            if (source is null)
            {
                throw new ArgumentNullException(nameof(source));
            }
            if (keySelector is null)
            {
                throw new ArgumentNullException(nameof(keySelector));
            }
            if (comparer is null)
            {
                throw new ArgumentNullException(nameof(comparer));
            }

            IList<TSource> result = new List<TSource>();
            using IEnumerator<TSource> enumerator = source.GetEnumerator();

            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                TKey lastKey = keySelector(element);

                result.Add(element);

                while (enumerator.MoveNext())
                {
                    element = enumerator.Current;
                    TKey newKey = keySelector(element);
                    int compare = descending ? comparer.Compare(lastKey, newKey) : comparer.Compare(newKey, lastKey);

                    if (0 <= compare)
                    {
                        result.Add(element);
                        lastKey = newKey;
                    }
                }
            }

            return (IReadOnlyList<TSource>)result;
        }
    }
}

Kotlin

StalinSort.kt
fun main(args: Array<String>) {
    println("Hello Stalin!")
    writeStalinSort(intArrayOf(4))
    writeStalinSort(intArrayOf(6, 2, 5, 7, 3, 8, 8, 4))
    writeStalinSort(intArrayOf(5, 3, 7, 8, 9, 5, 3, 5, 7))
    /**
     * Hello Stalin!
     * Input: 4
     * StalinBy: 4
     * StalinByDescending: 4
     * Input: 6,2,5,7,3,8,8,4
     * StalinBy: 6,7,8,8
     * StalinByDescending: 6,2
     * Input: 5,3,7,8,9,5,3,5,7
     * StalinBy: 5,7,8,9
     * StalinByDescending: 5,3,3
     */
}

private fun writeStalinSort(source: IntArray) {
    println("Input: ${source.joinToString(",")}")
    println("StalinBy: ${source.asSequence().stalinBy().joinToString(",")}")
    println("StalinByDescending: ${source.asSequence().stalinByDescending().joinToString(",")}")
}

fun <T> Sequence<T>.stalinBy(): List<T> where T : Comparable<T> {
    return stalinSort(this, false)
}

fun <T> Sequence<T>.stalinByDescending(): List<T> where T : Comparable<T> {
    return stalinSort(this, true)
}

private fun <T> stalinSort(source: Sequence<T>, descending: Boolean): List<T> where T : Comparable<T> {
    val iterator = source.iterator()
    val result = mutableListOf<T>()

    if (iterator.hasNext()) {
        var lastElement = iterator.next()
        result.add(lastElement)

        while (iterator.hasNext()) {
            val element = iterator.next()
            val compare = when (descending) {
                true -> element <= lastElement
                false -> lastElement <= element
            }
            if (compare) {
                result.add(element)
                lastElement = element
            }
        }
    }

    return result
}

Crystal

最近少しずつ学び始めてるCrystal(C#, Kotlinより雑いのは許して)

stalin_sort.cr
# Crystal 0.27.2 [60760a546] (2019-02-05)
# LLVM: 4.0.0
# Default target: x86_64-unknown-linux-gnu

puts "Hello Stalin!"
write_stalin_sort [4]
write_stalin_sort [6, 2, 5, 7, 3, 8, 8, 4]
write_stalin_sort [5, 3, 7, 8, 9, 5, 3, 5, 7]

# Hello Stalin!
# Input: [4]
# StalinBy: [4]
# StalinByDescending: [4]
# Input: [6, 2, 5, 7, 3, 8, 8, 4]
# StalinBy: [6, 7, 8, 8]
# StalinByDescending: [6, 2]
# Input: [5, 3, 7, 8, 9, 5, 3, 5, 7]
# StalinBy: [5, 7, 8, 9]
# StalinByDescending: [5, 3, 3]

def write_stalin_sort(source : Array(Int32))
  puts "Input: #{source}"
  puts "StalinBy: #{stalin_by source}"
  puts "StalinByDescending: #{stalin_by_descending source}"
end

def stalin_by(source : Array(Int32))
  stalin_sort source, false
end

def stalin_by_descending(source : Array(Int32))
  stalin_sort source, true
end

def stalin_sort(source : Array(Int32), descending : Bool)
  if source.size <= 1
    return source
  end

  result = Array(Int32).new
  lastElement = source[0]
  result << lastElement

  i = 1
  while i < source.size
    element = source[i]
    compare = if descending
                element <= lastElement
              else
                lastElement <= element
              end
    if compare
        lastElement = element
        result << element
    end

    i += 1
  end

  result
end

Repository

ソースはGitHubに置いてます

GitHubにリポジトリー置いてるときにTopic登録されてるなーと思ったら更なる先駆者がいた模様

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away