DouKaku? 6646 ika: Counting sort(比較しないソートの作成)

Comment detail

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?

Comment detail

Index

Feed

Other

Link

Pathtraq