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

Squeak Smalltalk で。

| sort |
sort := [:min :max :size :data |
    | bag out |
    bag := data asBag.
    out := OrderedCollection new: size.
    min to: max do: [:each |
        (bag occurrencesOf: each) timesRepeat: [out add: each]].
    out asArray].

sort valueWithArguments: #(-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;
    }
}

クイックソート的にやりました。しかし、終了条件が悪いので遅いです。

import Data.List (group,sort)

main :: IO ()
main = print $ qsort (-1) 10 [-1,9,4,8,9,6,3,9,5,2]

uniq :: Ord a => [a] -> [a]
uniq ns = map head $ group $ sort ns

qsort :: Integral a => a -> a -> [a] -> [a]
qsort _ _ [] = []
qsort _ _ ns | length (uniq ns) == 1 = ns
qsort min max ns = let mid = div (max + min) 2
                   in qsort min mid [y | y <- ns, y < mid] ++ qsort mid max [y | y <- ns, y >=mid ]

counting sortを実装しました。

import java.util.Arrays;

public class Sample187 {
    public static int[] countingSort(int min, int max, int[] data) {
        int[] counter = new int[max - min + 1];
        for (int i: 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});
        System.out.println(Arrays.toString(sort));
    }
}

バケツで。

see: バケットソート

<?php
$min = -1;
$max = 10;
$input = array(-1, 9, 4, 8, 9, 6, 3, 9, 5, 2);
$sorted = bucketsort($min, $max, $input);

function bucketsort($min, $max, $input){
    for($i = $min; $i <= $max; $i++)
        $temp[$i] = 0;
    foreach($input as $v)
        $temp[$v]++;
    foreach($temp as $k => $v)
        for($i = 0; $i < $v; $i++)
            $sorted[] = $k;
    return $sorted;
}

初投稿です。勢いで作ったので例外処理とか入ってません。

#include<stdio.h>

void sort(int min, int max, int len, int data[], int *result);

int main()
{
        int min = -1;
        int max = 10;
        int data[] = {-1, 9, 4, 8, 9, 6, 3, 9, 5, 2};
        int len = 10;
        int i;
        int *result;

        sort(min, max, len, data, result);
        for(i = 0; i < len; i++)
        {
                printf("%d\n", result[i]);
        }

        return 0;
}

void sort(int min, int max, int len, int data[], int * result)
{
        int bucket[len];
        int i, j;
        int idx = 0;

        for(i = min; i < max; i++)
        {
                bucket[i] = 0;
        }

        for(i = 0; i < len; i++)
        {
                bucket[data[i]]++;
        }


        for(i = min; i < max; i++)
        {
                for(j = 0; j < bucket[i]; j++)
                {
                        result[idx++] = i;
                }
        }
}

Mosh (Scheme) で書きました。データ個数を終了条件に使えばもっと効率よくできそうです。

(define count-sort (lambda (range-min range-max range-len data)
  (let loop1 ((i range-min) (result '()))
    (if (>= i range-max)
      result
      (loop1 (+ i 1) (append result
        (let loop2 ((ls data) (rs '()))
          (if (pair? ls)
            (loop2 (cdr ls) (if (= i (car ls)) (cons i rs) rs))
            rs))))))))

(write (count-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
(newline)

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 + " ");
    }
}

しまった。。。
バケットソートというのがあるんですね。
あんまり余裕がないので Gauche で書き直し。

(use gauche.sequence)

(define bucket-sort (lambda (range-min range-max data-len data)
  (let* ((range-len (+ 1 (- range-max range-min)))
         (bucket (make-vector range-len 0))
         (result '()))
    (for-each (lambda (i)
      (let ((j (- i range-min)))
        (vector-set! bucket j (+ 1 (vector-ref bucket j)))))
      data)
    (for-each-with-index
      (lambda (i count)
        (set! result (append result
          (make-list count (+ i range-min)))))
      bucket)
    result)))

(define main (lambda (args)
  (write (bucket-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
  (newline)
  0))

JavaScript。クイックソート、かな？
効率悪そう。

Array.prototype.sort2 = function(minVal, maxVal) {
    if (this.length <= 1) return this;
    var mid = (minVal + maxVal) / 2;
    var lt = [], eq = [], gt = [];
    for (var i=0; i < this.length; i++) {
        if (this[i] > mid)
            gt.push(this[i]);
        else if (this[i] < mid)
            lt.push(this[i]);
        else
            eq.push(this[i]);
    }
    return lt.sort2(minVal, mid).concat(eq, gt.sort2(mid, maxVal));
};

[-1,9,4,8,9,6,3,9,5,2].sort2(-1,10)

おっと。無駄が多すぎた。
以下の修正で関数に入る回数が109→15に改善しました。

3c3
<       var mid = (minVal + maxVal) / 2;
---
>       var mid = Math.floor((minVal + maxVal) / 2);

データのレンジがわかっているのであらかじめ順番に並んでいる結果のリストから入力リストにはいっているものだけ残すという方法です…

入力リストの要素数は必要ありません…

module Main where

sort_noComp :: (Num a, Ord a, Enum a)=> a -> a -> Int -> [a] -> [a]
sort_noComp min max len xs = filter (\x -> elem x xs) [min..max]

main = print $ sort_noComp 1 9 8 [4, 8, 9, 6, 3, 9, 5, 2]

baalさんの #6653 を参考にバケットソートで書いてみました。

(bucket-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2))
;=> (-1 2 3 4 5 6 8 9 9 9)

(defun bucket-sort (min max size data)
  (declare (integer min max size) (list data))
  (loop :with tem := (make-array (max size (- max min)) :initial-element () )
        :for item :of-type integer :in data
        :do (push item (svref tem (- item min)))
        :finally (return (reduce #'nconc tem))))

アルゴリズム的にはcounting sort相当になると思います。

1
2
3

sort.uncompare <- function(min, max, num, l){
   unlist(sapply(min:max, function(n)(l[l==n])))
}

これでいいのかな。

def sort(min, max, a):
    counts = [0] * (max - min + 1)
    for x in a:
        counts[x - min] += 1
    result = []
    for i, count in enumerate(counts):
        for _ in xrange(count):
            result.append(i + min)
    return result

def main():
    print sort(-1, 10, [-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])

if __name__ == '__main__':
    main()

uniq の中で sort を使ってしまっていますよ。(^_^;)

重複する要素が一個にまとめられてしまいます。

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;
    }
}

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

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();
    }
}

途中で (max-min+1)*n の配列ができちゃう。メモリ使いすぎ。

sortx=:3 :0
  min=. 0 { y
  max=. 1 { y
  n=. 2 { y
  a=. 3 }. y
  b=. min + i. 1 + max - min
  (+/"1 b =/ a) # b
)

mc さんの #6658 を参考にして、だいぶすっきりしたコードになりました。
ありがとうございます。

(define bucket-sort (lambda (range-min range-max data-len data)
  (let ((bucket (make-vector (+ 1 (- range-max range-min)) '())))
    (for-each
      (lambda (i)
        (let ((j (- i range-min)))
          (vector-set! bucket j (cons i (vector-ref bucket j)))))
      data)
    (fold-right append '() (vector->list bucket)))))

短くする方向で書いてみました。個数は要りません。

1	mysort min max ns = concat [filter (== x) ns \| x <- [min..max]]

こんな感じでしょうか。配列と最小値だけ必要です。

●sort(data,min)
    tmpとは配列
    bufとは配列
    iとは整数
    dataを反復
        tmp[対象-min]=tmp[対象-min]+1
    iで0から(tmpの配列要素数)-1まで繰り返す
        (tmp[i])回
            bufにi+minを配列追加
    bufで戻る

a="-1 9 4 8 9 6 3 9 5 2"を" "で区切る
sort(a,-1)を表示

あぁ、情けなし。

module Main where

sort_noComp min max xs = foldr (addCount) (map (flip (,) $ 0) [min..max]) xs >>= \(x, c) -> replicate c x
    where
        addCount :: Int -> [(Int, Int)] -> [(Int, Int)]
        addCount i [] = []
        addCount i ((j, x):xs)
            | i == j = (j, x + 1) : xs
            | otherwise = (j, x) : addCount i xs

main = print $ sort_noComp 1 9 [4, 8, 9, 6, 3, 9, 5, 2]

counting sortを実装しました。
> ghc --make -O2 CountingSort.hs
> ./CountingSort

import qualified Data.Map as M
import Control.Monad.State

counter min max xs = recur (M.fromAscList $ zip [min..max] (repeat 0)) xs
  where recur ctr [] = M.toAscList ctr
            recur ctr (x:xs) = recur (M.update (\v -> Just (succ v)) x ctr) xs

countingSort :: (Ord a, Enum a, Num a) => a -> a -> [a] -> [a]
countingSort min max xs = let ctr = counter min max xs
                                           result = M.fromAscList $ zip [0..len] (repeat 0)
                                      in evalState (countingSort_S min ctr) (0,result)
  where len = fromIntegral $ length xs - 1

countingSort_S :: (Ord a, Enum a, Num a) => a -> [(a,a)] -> State (a,M.Map a a) [a]
countingSort_S _ [] = get >>= return . M.elems . snd
countingSort_S min ((x,y):xs) = do
    forM_ [1..y] update
    countingSort_S min xs
  where update _ = do
                (index,result) <- get
                put (succ index, M.update f index result)
            f _ = Just x

main :: IO ()
main = do
    print $ countingSort (-1) 10 [-1,9,4,8,9,6,3,9,5,2]
    print $ countingSort (-100000) 100000 [-100000..100000]

ちょっと修正しました。

import qualified Data.Map as M                                                                                               
import Control.Monad.State

counter min max xs = recur (M.fromAscList $ zip [min..max] (repeat 0)) xs
  where recur ctr [] = M.toAscList ctr 
        recur ctr (x:xs) = recur (M.update (\v -> Just (succ v)) x ctr) xs

countingSort :: (Ord a, Enum a, Num a) => a -> a -> [a] -> [a] 
countingSort min max xs = let ctr = counter min max xs
                          in evalState (countingSort_S min ctr) []
  where len = fromIntegral $ length xs - 1 

countingSort_S :: (Ord a, Enum a, Num a) => a -> [(a,a)] -> State [a] [a] 
countingSort_S _ [] = get >>= return . reverse
countingSort_S min ((x,y):xs) = do
    forM_ [1..y] (\_ -> get >>= \xs -> put $ x:xs)
    countingSort_S min xs

main :: IO ()
main = do
    print $ countingSort (-1) 10 [-1,9,4,8,9,6,3,9,5,2]
    print $ countingSort (-100000) 100000 [-100000..100000]

listを何回も作っているのがダサいです。アルゴリズムとしてはradix sort系です。

def nocmpsort(min, max, count, data):
  """
    >>> nocmpsort(min=-1, max=10, count=10,\
          data=[-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])
    [-1, 2, 3, 4, 5, 6, 8, 9, 9, 9]
  """
  latitude = max - min
  base = 0
  x = 1
  while latitude > x:
    x = x << 1
    base += 1
  def encode(e):
    return e - min
  def decode(d):
    return d + min
  def nocmpsort_binary(data):
    """
    >>> base =  5
    >>> nocmpsort_binary([0, 10, 5, 9, 10, 7, 4, 10, 6, 3])
    [0, 3, 4, 5, 6, 7, 9, 10, 10, 10]
    """
    bin = list()
    for i in range( 2 << base):
      bin.append(0)
    for d in data:
      bin[d]+=1
    r = list()
    for i, count in enumerate(bin):
      while count > 0:
        r.append(i)
        count -=1
    return r

  return map(decode, nocmpsort_binary(map(encode, data)))

再帰をつかった基数2のバージョン

def nocmpsort(min, max, count, data):
  """
    >>> nocmpsort(min=-1, max=10, count=10,\
          data=[-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])
    [-1, 2, 3, 4, 5, 6, 8, 9, 9, 9]
  """
  latitude = max - min
  base = 0
  x = 1
  while latitude > x:
    x = x << 1
    base += 1
  def encode(e):
    return e - min
  def decode(d):
    return d + min
  def nocmpsort_binary(data):
    """
    >>> base =  5
    >>> nocmpsort_binary([0, 10, 5, 9, 10, 7, 4, 10, 6, 3])
    [0, 3, 4, 5, 6, 7, 9, 10, 10, 10]
    """
    def binary(base, data):
      if base == -1:
        r = list(data)
        return r
      assert base > -1
      small = list()
      big = list()
      mask = 1 << base
      for d in data:
        if mask & d:
          big.append(d)
        else:
          small.append(d)
      r = binary(base - 1, small)
      r.extend(binary(base - 1, big))
      return r
    return binary(base, data)

  return map(decode, nocmpsort_binary(map(encode, data)))

if __name__ == "__main__":
  import doctest
  doctest.testmod()

counting sort
配列を使って素朴に。

import Array
import List

countingSort lower upper n xs = elems $ array (1,n) ys  where
  lower1 = lower - 1
  -- キーの出現回数
  a = accumArray (+) 0 (lower1,upper) [(x,1)| x <- xs]
  -- 出現回数の累計
  b = array (lower1,upper) $ (lower1,0): [(i,b!(i-1)+a!i)| i <- [lower..upper]]
  -- ソート後のキーの位置の計算
  (_,ys) = mapAccumL f b xs
  f c x = (c//[(x,(c!x)-1)], (c!x,x))

{-
> countingSort (-1) 10 10 [-1,9,4,8,9,6,3,9,5,2]
[-1,2,3,4,5,6,8,9,9,9]
-}

以下のリスト内包表記内でも比較が使われていますね。

1	[y \| y <- ns, y < mid] ++ qsort mid max [y \| y <- ns, y >=mid ]

バケットソートって知らなかったのでやってみました。

でもこの実装だと要素作り直しててソートつーのかなんだか。

def bucket_sort(ary, min, max);
  bucket = Array.new(max-min+1, 0)
  ary.each{|num|
    bucket[num-min]+=1
  }

  ret = []
  bucket.each_with_index{|count, index|
    ret += [index+min] * count
  }
  ret
end

ary = [-1,9,4,8,9,6,3,9,5,2]
p bucket_sort(ary, ary.min, ary.max)

perlが無かったので。
アルゴリズムはバケツソートです。

use strict;

sub bucket_sort
{
  my ($min, $max, $num, @data) = @_;

  my @bucket;
  eval {
    for ( map { [$_ - $min,$_] } @data) {
      $bucket[$_->[0]] = [] if !$bucket[$_->[0]];
      push @{$bucket[$_->[0]]}, $_->[1];
    }
  };
  if ( $@ ) {
    bucket_sort($min-1,$max,$num,@data);
  }
  else {
    map { @$_ } grep { $_ } @bucket;
  }
}

$,=', '; $\="\n";
print bucket_sort(qw/-1 10 10 -1 9 4 8 9 6 3 9 5 2/);
print bucket_sort(qw/1 10 10 -1 9 4 8 9 6 3 9 5 2/);

問題文に
「最大値や最低値を元に算出した数値との比較は使用しても問題ありません。」
とあるのでその比較は問題ないんじゃないでしょうか。

皆さんのコードを参考に実装してみましたが、イテレータのサンプルみたいになってしまいました orz

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template<typename InputIterator, typename OutputIterator>
void sort(int min, int max, InputIterator begin, InputIterator end, OutputIterator dst)
{
    std::vector<int> counts(max - min + 1);
    for(InputIterator i = begin; i != end; ++i)
    {
        ++counts[*i - min];
    }

    for(std::size_t i = 0; i < counts.size(); ++i)
    {
        std::vector<int> c(counts[i], i + min);
        std::copy(c.begin(), c.end(), dst);
    }
}

int main(int, char* [])
{
    static const int array[] = { -1, 9, 4, 8, 9, 6, 3, 9, 5, 2 };
    std::vector<int> dst;

    // ソート; dst に並べ替えられた値が入ります
    sort(-1, 10, array, array + (sizeof(array) / sizeof(*array)), std::back_inserter(dst));

    // 結果表示
    std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, ", "));

    return 0;
}

比較していないかといわれると
しているような気もします。

お題をどう理解するかで変わってきますね。

def sort( min, max, count, list ){
   def larges = list.findAll{ it >= max }
   list -= larges
   def smalls = list.findAll{ it <= min }
   list -= smalls

   smalls + ((list.empty)?[]:sort(min-1, max-1, list.size(), list)) + larges
}

// 試行
def list = [-1,9,4,8,9,6,3,9,5,2]
println  sort(-10, 10, list.size(), list)

素直に単純なビンソートで。

(use srfi-1)
(use srfi-43)

(define (bin-sort vmin vmax n xs)
  (let ((v (make-vector (- vmax vmin -1) 0)))
    (for-each (lambda (x)
                (inc! (ref v (- x vmin))))
              xs)
    (concatenate
     (vector-fold-right (lambda (i knil x)
                          (cons (make-list x (+ i vmin)) knil))
                        '() v))))

(define (main args)
  (print (bin-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
  0)

PostScriptで、radix sort 基数2 です。特にかわったことはやっていない筈です。

%!PS

/AddToVector { % val [Vector]  AddToVector  [NewVector]
    [ 3 1 roll
    {
        1 index add exch
    } forall
    pop
    ]
} bind def

/RadixSortCore { % [Vector]  max  RadixSortCore  [NewVector]
    5 dict begin 
    /Max exch def
    /Vect exch def
    /Radix 1 def
    {
        /Vect
        [
            Vect {
                dup Radix and 0 ne {
                    pop
                } if
            } forall
            Vect {
                dup Radix and 0 eq {
                    pop
                } if
            } forall
        ] def
        Radix Max gt { exit } if
        /Radix Radix dup add def
    } loop
    Vect
    end
} bind def

/RadixSort { % min max [Vector] RadixSort [NewVector]
    2 index neg exch AddToVector exch 2 index sub
    RadixSortCore
    AddToVector
} bind def

% ============ Test Code ==============
-1024 2048 [ -510 10 7 12 45 120 -1024 -511 -512 249 1238 1274 ] RadixSort ==

適当に書いていたら、quicksortのように
Pivotとして実際の要素を使えないので、
場合分けで結構バグってしまいました（恥
これもバグってるかも。

>c(sort).
{ok,sort}
> sort:main(-1,10,10, [-1,9,4,8,9,6,3,9,5,2]).
[-1,2,3,4,5,6,8,9,9,9]

-module(sort).
-export([main/4]).

main(Min, Max, _Num, List) ->
   sort(Min, Max, List).

sort(_Min, _Max, []) -> [];
sort(_Min, _Max, [H|[]]) -> [H];
sort(Min, Min, List) -> List;
sort(Min, Max, List) ->
    Pivot = Min + ((Max - Min) div 2),
    sort(Min,Pivot, [ X || X <- List, X < Pivot ])
    ++
    [ X || X <- List, X =:= Pivot ]
    ++
    sort(Pivot+1, Max, [ X || X <- List, X > Pivot ]).

scalaが出ていない様なので。

object BucketSort {
    def sort(min:Int,max:Int,data:Array[Int]):Array[Int] = {
        (min to max).flatMap { d => data.filter { _ == d } }.toArray
    }
    def main(args:Array[String]):Unit = {
        Console.println(BucketSort.sort(-1,10,Array(-1,9,4,8,9,6,3,9,5,2)).toString)
    }
}

バケットソートです。ワンライナーで書いてみました。
最大値と個数は無視します。

1	($n,$x,$c,@s)=@ARGV;$b[$_-$n]++for@s;$b[$_]&&print(($_+$n.' ')x$b[$_])for 0..$#b

バケツソート。無理矢理感有り。
JScript(WSH)。

-------------------------------
C:\temp>cscript /nologo bucketsort.js
-1 2 3 4 5 6 8 9 9 9

function bucketsort(data,min,max,size){
  var result=[];
  eval( data.replace(/(-?\d+)/g,'result[$1-min]+=",$1,";') );
  return result.join('').split(/[^0-9-]+/).join(' ');
}

WScript.Echo(bucketsort('-1 9 4 8 9 6 3 9 5 2','-1','10','10'));

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 + " ");
    }
}

こんなのでもいいのかな. マッチしたオブジェクトを格納するようなメソッドってなかったっけ.

def main(min, max, num, ary)
  [*min..max].map{|i| ary.select{|j| i == j}}.flatten
end
min, max, num = 1, 10, 10
p ary = num.times.map{(rand*(max-min)).round+min}
p main(min, max, num, ary)

半年も前のお題でしたが、Rubyの勉強でやってみました。
radix sort の基数２で、かつインデックスソートです。
bin sort．．．ではないと思います。多分。

最下２行は#6703さんを参考にさせて頂きました。
ありがとうございます。

def radixsort(minnum, maxnum, cnt, numlist);
  bin = [[[*0..cnt-1],[]],[[],[]]]  # ソート用インデックス
  ref = 1   # 参照値
  idx = 0   # ビン1参照用
  ridx = 1  # ビン2参照用
  while ref < (maxnum-minnum)
    for i in 0..1
      bin[i][idx].each do |b|
        if (ref & (numlist[b]-minnum)) == 0
          bin[0][ridx].push(b)
        else
          bin[1][ridx].push(b)
        end
      end
      bin[i][idx].clear
    end
    # インデックス反転
    idx = ridx
    ridx= (ridx-1).abs
    # 参照値ビットシフト
    ref <<= 1
  end

  ret = numlist.values_at(*(bin[0][idx]+bin[1][idx]))
  ret
end

ary = [-1,9,4,8,9,6,3,-5,9,5,2]
p radixsort(ary.min, ary.max, ary.length, ary)

LINQって便利ですね。
ところで、マイナス値が複数あるとどういう結果になりますか？
大分期間が経ってしまっていますが、試せる環境を準備できなくて
気になりましたので．．．

マイナスの値が複数でも大丈夫です。

ソート前 2147483647 -1 2 0 -2 1 -2147483648

ソート後 -2147483648 -2 -1 0 1 2 2147483647

結局のところやってることは

1.符号なし整数とみなしてソート

2.配列の前後を入れ替える

0x00000000..0x7FFFFFFF,0x80000000..0xFFFFFFFF <- before

0x80000000..0xFFFFFFFF,0x00000000..0x7FFFFFFF <- after

マイナスの値は２の補数で表現されていることが条件

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] numbers = { int.MaxValue, -1, 2, 0, -2, 1, int.MinValue };

        foreach (var item in RadixSort(numbers))
        {
            Console.Write(item + "  ");
        }
        Console.WriteLine();
    }

    static int[] RadixSort(int[] a)
    {
        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();
    }
}

ありがとうございます。お騒がせしてすみませんでした。ビット演算は久しくやっていなかったので思い違いしてしまったようです。

なんでこれに SQL がないんだろ・・・

ということで、SQL Server 2008 で確認しましたが、共通表式が使える RDBMS ならどれでも同じように動くはずです。

共通表式がない RBDMS でも、なんか適当なテーブルにデータを INSERT して取り出すだけです。

WITH
  Input(n) AS (
    SELECT -1
    UNION ALL SELECT 9
    UNION ALL SELECT 4
    UNION ALL SELECT 8
    UNION ALL SELECT 9
    UNION ALL SELECT 6
    UNION ALL SELECT 3
    UNION ALL SELECT 9
    UNION ALL SELECT 5
    UNION ALL SELECT 2
  )
SELECT
    n
FROM
    Input
ORDER BY
    n

DouKaku?

比較しないソートの作成

Posted feedbacks - Flatten

Index

Feed

Other

Link

Pathtraq