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

post comment

Posted feedbacks - C++

皆さんのコードを参考に実装してみましたが、イテレータのサンプルみたいになってしまいました 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;
}

DouKaku?

比較しないソートの作成

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq