ネットで少しだけ話題になったネタ系ソートアルゴリズムのスターリンソート（というかフィルター？）をC#とC++で実装してみようと思います。
スターリンソートとは？
まず、スターリンソートの簡単な説明です。
スターリンソートは、ソートアルゴリズムの一種（自称）で計算量はなんとO(n)です。
N個の配列であれば、おおよそ、配列を末尾から先頭までを1回だけ巡回するとソートが完了するアルゴリズムらしいです。
通常のソートだと、O(n2)回や、O(n log n)回計算しないとソートできませんがそれらに比べ圧倒的に高速です。（本来ならあり得ないはず！）
C#の実装
ではまずは、一番よく使うC#で確認と実装してきます。
オリジナルの実装
GitHubで元のコードが公開されているので引用します。
static private int[] stalinSort(int[] array) { if (array.Length == 0) return array;//empty array is already sorted. yay! var sortedArray = new List<int>() { array[0] }; //resulting array always contains the first element for (int i = 1; i < array.Length; i++) { if (array[i] >= sortedArray.Last()) sortedArray.Add(array[i]); } return sortedArray.ToArray(); } static void Main(string[] args) { int[] array = new int[]{1, 2, 4, 3, 6, 8, 0, 9, 5, 7}; int[] sortedArray = stalinSort(array); Console.WriteLine("{0}", string.Join(", ", sortedArray)); }
このコードは実行すると以下のように出力されます。
// > 1, 2, 4, 6, 8, 9
ネタバレになりますが、ソートじゃないじゃん！！
という突っ込みはさておき、共産主義圏でよくある(？)「粛清」によって数列がソート（≒フィルター）されました。
直前に出現した数値より小さい値が後続に出現すると粛清を行いソートを実行しています。
少し改造してみる
このアルゴリズムですが、int配列しか対応していないので、「自作オブジェクトのソート機能拡張」と、運搬性を持たせるために「クラス化」してみようと思います。
少し長いですが以下の通りです。
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace System.Sort { internal class Program { public static void Main(string[] args) { // 公式サンプルと同じ結果になる int[] array = new int[] { 1, 2, 4, 3, 6, 8, 0, 9, 5, 7 }; int[] sortedArray = Stalin.Sort(array); Console.WriteLine(string.Join(", ", sortedArray)); // 出力 // > 1, 2, 4, 6, 8, 9 // 自作オブジェクトオブジェクトをスターリンソートする var array2 = new List<Person>() { new Person("Lenin", 1), new Person("Stalin", 2), new Person("Malenkov", 4), new Person("Takap", 3), new Person("Khrushchev", 6), new Person("Breznev", 8), new Person("Takap", 0), new Person("Andropov", 9), new Person("Takap", 5), new Person("Takap", 7), }; Stopwatch sw = Stopwatch.StartNew(); string str = ""; Person[] sortedArray2 = Stalin.Sort(array2.ToArray(), p => p.Age); Array.ForEach(sortedArray2, p => str += $", {p.Age}({p.No})"); Console.WriteLine(str.Trim(' ', ',')); // 出力 // > 1(Lenin), 2(Stalin), 4(Malenkov), 6(Khrushchev), 8(Breznev), 9(Andropov) sw.Stop(); Console.WriteLine(sw.Elapsed.TotalMilliseconds); str = ""; IEnumerable<Person> sortedArray3 = Stalin.Sort2(array2, p => p.Age); foreach (var p in sortedArray3) { str += $", {p.Age}({p.No})"; } Console.WriteLine(str.Trim(' ', ',')); // 出力 // > 1(Lenin), 2(Stalin), 4(Malenkov), 6(Khrushchev), 8(Breznev), 9(Andropov) } } // 自作のクラス public class Person { public Person(string no, int age) { this.No = no; this.Age = age; } public string No { get; set; } public int Age { get; set; } } public static class Stalin { // もともとのソート方法 public static int[] Sort(int[] array) { if (array.Length == 0) { // empty array is already sorted. yay! return array; } // resulting array always contains the first element var sortedArray = new List<int>() { array[0] }; for (int i = 1; i < array.Length; i++) { if (array[i] >= sortedArray.Last()) { sortedArray.Add(array[i]); } } return sortedArray.ToArray(); } // 任意の型でスターリンソートする // -> 述語にTをintに変換する条件を記述する public static T[] Sort<T>(T[] array, Func<T, int> toIntFunc/* object to int conversion condition */) { if (array.Length == 0) { return array; } var sortedArray = new List<T>() { array[0] }; int last = toIntFunc(array[0]); for (int i = 1; i < array.Length; i++) { int current = toIntFunc(array[i]); if (current >= last) { last = current; sortedArray.Add(array[i]); } } return sortedArray.ToArray(); } // 任意の型でスターリンソートするその(2) // -> C#のリスト配列ならすべて取り扱えるように改変 & シーケンスで O(n) 感を出す public static IEnumerable<T> Sort2<T>(IEnumerable<T> array, Func<T, int> toIntFunc) { int? last = null; foreach (var item in array) { int current = toIntFunc(item); if (last == null) { last = current; yield return item; } else if (current >= last) { last = current; yield return item; } } } } }
C#の配列などのリスト要素はおおむねIEnumerable
ジェネリックに指定したTをint型へ変換する変換規則を述語によって指定します。かなり速度が低下しますが、述語に指定したラムダによって比較が可能になるので同じ結果がオブジェクト配列からも得られます。
C++で実装
次に、ゲーム制作で使用してるC++で実装します。
オリジナルの実装
こちらも、GitHubで元のコードが公開されているので引用します。
#include <iostream> #include <vector> void stalinSort(std::vector<int> &arr, std::vector<int> &sorted) { sorted.push_back(arr[0]); for (int i = 1, j = 0; i < arr.size(); i++) { if (arr[i] > arr[j]) { sorted.push_back(arr[i]); j++; } } } int main() { std::vector<int> arr = {1, 2, 4, 3, 8, 0, 9, 5, 7}; std::vector<int> sortedArr; stalinSort(arr, sortedArr); std::cout << "before\n"; for (int a : arr) { std::cout << a << ", "; } std::cout << "\nafter\n"; for (int a : sortedArr) { std::cout << a << ", "; } std::cout << "\n"; return 0; }
実行すると以下数列を画面に出力します。
// > 1, 2, 4, 8, 9
C#版は'>='でC++版は'>'なんですね…(汗
それはさておき、こちらも大粛清が起きて数列がソートされました。
少し改造してみる
こちらも、int配列しか対応していないので、「自作オブジェクトのソート機能拡張」と、運搬性を持たせるために「クラス化」してみようと思います。
#include <iostream> #include <vector> #include <functional> class Stalin { public: static void sort(std::vector<int>& arr, std::vector<int>& sorted) { sorted.push_back(arr[0]); for (int i = 1, j = 0; i < arr.size(); i++) { if (arr[i] > arr[j]) { sorted.push_back(arr[i]); j++; } } } // テンプレート化してどんな型でも処理できる方式 // → 述語でTをintに変換する方法を教える template <typename T> static void sort(std::vector<T>& arr, std::vector<T>& sorted, const std::function<int(T)> toInt) { if (arr.size() == 0) { return; // already sorted. } int latest = toInt(arr[0]); // T -> int の変換量を減らすためのキャッシュ sorted.push_back(arr[0]); for (int i = 1, j = 0; i < arr.size(); i++) { int current = toInt(arr[i]); if (current > latest) { latest = current; sorted.push_back(arr[i]); j++; } } } // 三方比較演算子で比較自体を外に出す方式のソート // → 一個前のより効率が良くなる時だけ使用する(そんなケースないかも？) template <typename T> static void sort(std::vector<T>& arr, std::vector<T>& sorted, const std::function<int(T a, T b)> compare/* <=> three-way comparison */) { if (arr.size() == 0) { return; // already sorted. } sorted.push_back(arr[0]); for (int i = 1, j = 0; i < arr.size(); i++) { if(compare(arr[i], arr[j]) > 0) { sorted.push_back(arr[i]); j++; } } } }; int main() { std::vector<int> arr = { 1, 2, 4, 3, 8, 0, 9, 5, 7 }; std::vector<int> sortedArr; if (true) { Stalin::sort<int>(arr, sortedArr, [](auto p) { return p; }); } else { Stalin::sort<int>(arr, sortedArr, [](auto a, auto b) { return a - b; }); } std::cout << "before\n"; for (int a : arr) { std::cout << a << ", "; } std::cout << "\nafter\n"; for (int a : sortedArr) { std::cout << a << ", "; } std::cout << "\n"; return 0; }
作ってて思ったのですが、double型とかはintへの変換いらないので特殊化しておくべきでしたね…
こちらは、C#版と同じ方式と、三方比較演算子で比較自体を外に出す方式を実装してみました。後述のほうはオブジェクトをintに変換する処理が結構呼ばれるので前者に比べると少し効率が悪いかもしれません？ｗ
なんでスターリンソートなのか？
スターリンさん「大粛清」で有名みたいです。ネット掲示板でめちゃくちゃ浅いレベルでしか知らなかったのですがこれはヤバいですね。
最後に
ちょっとした笑いと歴史の勉強になりました。
以上です。
