C++編 逆引き 配列をソートする

先頭へ戻る

目的

配列の要素を、それらの要素の値の昇順や降順になるように並び替える(ソート)したいとします。

以下のような配列があるとして、

int array[] = {5, 4, 7, 2, 8, 7, 3};

昇順であれば {2, 3, 4, 5, 7, 7, 8} という順番に、降順であれば {8, 7, 7, 5, 4, 3, 2} という順番になるようにします。

方法①(std::sort関数や std::stable_sort関数を使う)[C++03~]

標準ライブラリの std::sort関数(【標準ライブラリ】第22章)や、std::stable_sort関数(【標準ライブラリ】第22章)を使うのが簡単です。この方法は、配列だけでなく、コンテナ類でも使用できます。

速度面では std::sort関数の方が有利ですが、std::sort関数は安定(アルゴリズムとデータ構造編【整列】第0章)ではありません。使い方はどちらも同じです。

昇順にソートする場合は、以下のようにします。

#include <algorithm>
#include <iostream>

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

namespace {
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << std::ends;
        }
        std::cout << std::endl;
    }
}

int main()
{
    int array[] = {5, 4, 7, 2, 8, 7, 3};

    std::sort(array, array + SIZE_OF_ARRAY(array));
    printElems(array, array + SIZE_OF_ARRAY(array));
}

実行結果:

2 3 4 5 7 7 8

C++11 では、std::begin(array) や std::end(array) のようにして、配列の先頭や末尾(の次)を指すポインタを得られます。

降順でソートしたい場合は、第3引数に std::greater を指定します。

#include <algorithm>
#include <functional>
#include <iostream>

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

namespace {
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << std::ends;
        }
        std::cout << std::endl;
    }
}

int main()
{
    int array[] = {5, 4, 7, 2, 8, 7, 3};

    std::sort(array, array + SIZE_OF_ARRAY(array), std::greater<>());
    printElems(array, array + SIZE_OF_ARRAY(array));
}

実行結果:

8 7 7 5 4 3 2

方法②(自力でソートする)[C++03~]

余計なバグを生む可能性を考えると、あまりはできませんが、性能上の問題等でやむを得ない場合には、自力でソートアルゴリズムを実装するという方法もあります。

ソートアルゴリズムにはいろいろな種類があるので、目的に合った性能を持ったアルゴリズムを比較・検討して、慎重に実装してください。基本的なソートアルゴリズムについては、アルゴリズムとデータ構造編を参照してください。


参考リンク



更新履歴

'2017/5/29 新規作成。



逆引きのトップページへ

C++編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー