比較しないソートの作成 in D 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

Counting sort

private import std.stdio;

void main() {
    int[] a = [1, 9, 4, 8, 9, 6, 3, 9, 5, 2];
    a.countingSort(1, 10);
    writeln(a);
}

void countingSort(int[] array, int min, int max) {
    auto counts = new uint[max - min + 1];
    foreach(n; array) {
        counts[n - min]++;
    }
    auto p = array.ptr;
    foreach(i, c; counts) {
        p[0..c] = i + min;
        p += c;
    }
}

Radix sort (内部アルゴリズムはBucket sort)

private import std.stdio, std.stdint;

void main() {
    int64_t[] a = [int64_t.max, 0, -1, 3, 1 << 17, -1 << 30, int64_t.min];
    writeln(a); // [9223372036854775807 0 -1 3 131072 -1073741824 -9223372036854775808]
    a.radixSort();
    writeln(a); // [-9223372036854775808 -1073741824 -1 0 3 131072 9223372036854775807]
}

private import std.traits : unsigned;

void radixSort(T)(T[] array) if(is(unsigned!(T))) {
    alias unsigned!(T) U;

    auto uarray = new U[array.length];
    foreach(i, ref n; uarray) {
        n = array[i] - T.min;
    }
    
    foreach(i; 0 .. T.sizeof * 8 / 4) {
        auto buckets = new U[][1 << 4];

        foreach(n; uarray) {
            buckets[n >> i * 4 & 0b1111] ~= n;
        }

        auto p = uarray.ptr;
        foreach(bucket; buckets) {
            p[0 .. bucket.length] = bucket;
            p += bucket.length;
        }
    }

    foreach(i, ref n; array) {
        n = uarray[i] + T.min;
    }
}

DouKaku?

比較しないソートの作成

Posted feedbacks - D

Index

Feed

Other

Link

Pathtraq