寝る前にTwitterを見てたらTLにこんなツイートが↓
ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019
寝る前に笑わせんなよ寝れねぇじゃねぇか！！ということで実装してみることに
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登録されてるなーと思ったら更なる先駆者がいた模様