比較しないソートの作成 in C# DouKaku?

ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。
・最低値・最大値・個数・並び替え対象の4つを引数として受け取る
・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。
・同値が複数出現することがある。
・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。
・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。
・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。
・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ)
・昇順降順はどちらでもかまいません

以下サンプル入出力
>>入力
-1 10 10
-1 9 4 8 9 6 3 9 5 2
>>出力
-1 2 3 4 5 6 8 9 9 9

horiuchiさんの#6648をコピペしてC#のコードに改変しました。
殆ど一緒です。行数まで一致しています。
JavaとC#って似てますよね。

using System;

public class Sample187 {
    public static int[] countingSort(int min, int max, int[] data) {
        int[] counter = new int[max - min + 1];
        foreach(int i in data) {
            counter[i - min]++;
        }

        int[] result = new int[data.Length];
        int index = 0;
        for(int i = 0; i < counter.Length; i++) {
            for(int count = 0; count < counter[i]; count++) {
                result[index++] = i + min;
            }
        }
        return result;
    }

    public static void Main(String[] args) {
        int[] sort = countingSort(-1, 10, new int[] { -1, 9, 4, 8, 9, 6, 3, 9, 5, 2 });
        foreach(int i in sort) Console.Write(i + " ");
    }
}

基数ソートです。引数の最大値と最小値はメソッド内で使用してません。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] x = { -1, 9, 4, 8, 9, 6, 3, 9, 5, 2 };

        foreach (var item in RadixSort(x, int.MinValue, int.MaxValue))
        {
            Console.Write(item + "  ");
        }
        Console.WriteLine();
    }

    static int[] RadixSort(int[] a, int min, int max)
    {
        for (uint x = 1; x != 0; x <<= 1)
        {
            a = a.Where(n => (n & x) == 0).Concat(a.Where(n => (n & x) != 0)).ToArray();
        }
        return a.SkipWhile(n => 0 <= n).Concat(a.TakeWhile(n => 0 <= n)).ToArray();
    }
}

LINQでぴしっとはまると気持ちいいですね。基数ソートのつもりでしたが、鳩の巣ソートらしいです。Mainは#6652から持ってきました、ありがとうございます。

using System;
using System.Linq;
using System.Collections.Generic;

class C
{
    static IEnumerable<int> countingSort(int[] src, int min, int max)
    {
        var l = src.ToLookup(i => i);
        return Enumerable.Range(min, max - min + 1).SelectMany(i => l[i]);
//こう書いても同じ
//        return from i in Enumerable.Range(min, max - min + 1)
//               from e in l[i]
//               select e;
    }

    static void Main()
    {
        var sort = countingSort(new int[] { -1, 9, 4, 8, 9, 6, 3, 9, 5, 2 }, -1, 9);
        foreach (var e in sort)
            Console.Write(e + " ");
    }
}

DouKaku?

比較しないソートの作成

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq