配列の並び替え

・概要

プログラミングで配列はごく基本的な概念で自分もよく利用します。というか配列がないとプログラムできません。MFCにも配列を扱うクラスがいくつかありますが、どれも配列内の並び替えができるメンバ関数がありません(VC++ 2005の場合)。　配列の並び替えは頻繁に行う作業ですし、ないと結構面倒です。ですから自分で実装することになりますが、並び替えのアルゴリズムはバブルソートとクイックソートの２種類あります。

前者はアルゴリズム自体は簡単ですがクイックソートに比べ速度がでません。ということで今回はクイックソートを配列を表すクラスに実装してみます。検索すればアルゴリズムはいくつものサイトで見つけられますが実際理解するのはちょっと難しいです。しかし、ランタイムライブラリでqsort関数というとても便利な関数があるのでこれを使って楽をします。

どのクラスに並び替えの機能を実装するかですが、MFC使いにとっては大部分の基底クラスになっているCObjectへのポインタの配列を扱うCObArrayでやってみたいと思います。

・準備

VS2005のファイル(F)→新規作成(N)→プロジェクト(P)から新規のプロジェクトを作成します。ダイアログボックスが表示されたら「Win32コンソールアプリケーション」を選択して任意のプロジェクト名を指定して次をクリックしてください。

アプリケーションウィザードの「アプリケーションの設定」画面で「共通ファイルヘッダーを追加」でMFCにチェックを入れて完了してください。

・CMyObjectの作成

アプリケーションウィザードで作成された _tmain関数はとりあえずそのままにして、並べ替えの対象となるCObjectの派生クラスを作成します。 VSのプロジェクト(P)→クラスの作成(C)からCObjectの派生クラスを作成してください。クラス名はCMyObjectとします。スケルトンができたら以下のヘッダファイル、実装ファイルのようにコーディングしてください。

//MyObject.hヘッダファイル

#pragma once
// CMyObject コマンドターゲット

class CMyObject : public CObject 
{
protected:
    int m_nValue; 

public:
    CMyObject();
    virtual ~CMyObject(); 

    int GetValue() const;  //値取得

    bool operator <(const CMyObject &obj) const;  //比較演算子オーバーロード
    bool operator >(const CMyObject &obj) const; 
    bool operator ==(const CMyObject &obj) const; 
};

// MyObject.cpp : 実装ファイル
//
#include "stdafx.h"
#include "testSort.h"    //アプリケーションヘッダファイル
#include "MyObject.h"

// CMyObject
CMyObject::CMyObject()
: m_nValue(rand())
{
}

CMyObject::~CMyObject()
{
}

// CMyObject メンバ関数
int CMyObject::GetValue() const 
{
    return m_nValue; 
}

bool CMyObject::operator <(const CMyObject &obj) const 
{
    return this->m_nValue < obj.m_nValue; 
}

bool CMyObject::operator >(const CMyObject &obj) const 
{
    return this->m_nValue > obj.m_nValue; 
}

bool CMyObject::operator ==(const CMyObject &obj) const 
{
    return this->m_nValue == obj.m_nValue; 
}

CMyObjectのm_nValueの値によってソートをします。各比較演算子のオーバーロードは qsort関数の第四引数で使用する比較関数内で使用するために実装しています。

・CSortArrayの実装

本題のクラスの実装ですが、本体自体はいたって簡単です。プロジェクト(P)→クラスの追加(C)からCObArrayの派生クラスを作成しますが、ウィザードではなぜか基本クラスにCObArrayを選択できません。とりあえずCObjectを基本クラスにして派生クラスを作成して後で修正します。

//SortArray.hヘッダファイル

#pragma once

// CSortArray コマンドターゲット
class CSortArray : public CObArray
{
protected:
    //比較関数
    static int __cdecl CompareFn(const CMyObject **ppFirst,
                                 const CMyObject **ppSecond);

public:
    CSortArray();          //コンストラクタ
    virtual ~CSortArray(); //デストラクタ

    void Sort(int (__cdecl *pfnCompare)(const CMyObject **pFirst,
                                        const CMyObject **pSecond) = CompareFn);
};

// SortArray.cpp : 実装ファイル
//
#include "stdafx.h"
#include "testSort.h"
#include "MyObject.h"    //インクルード
#include "SortArray.h"

// CSortArray
CSortArray::CSortArray()
{
}

CSortArray::~CSortArray()
{
}

// CSortArray メンバ関数

//並べ替え
void CSortArray::Sort(int (*pfnCompare)(const CMyObject **, const CMyObject **)
                                                                   /*=CompareFn*/)
{
    CObject **ppObj = GetData();
    ::qsort(ppObj, GetCount(), sizeof(CObject*),
                                    (int (*)(const void*, const void*))pfnCompare);
}

//比較関数
int CSortArray::CompareFn(const CMyObject **ppFirst, const CMyObject **ppSecond)
{
    if (**ppFirst < **ppSecond)       return -1;
    else if (**ppFirst == **ppSecond) return 0;
    else                              return 1;
}

ステップ数自体は少ないですが、関数へのポインタを指定しなければならないので表記がちょっとややこしいかもしれません。
CSortArray::Sort関数の引数に指定する関数へのポインタは、第一・第二引数がconst CMyObject*へのポインタで、int型の戻値です。戻値が負の値なら、第一引数が第二引数より前に並び替えられます。この関数の呼び出し規約は__cdeclであり、また、広域関数またはstaticなメンバ関数でなければならないので注意してください。(SortArray.hのCompareFnの宣言を注意してご覧ください。)

これでできあがりです。あとは使うだけ。qsort関数を使わずにクイックソートのアルゴリズムを自分で実装したら結構？長くなります。最後に_tmain関数で CSortArrayクラスを使ってみます。

・テスト

アプリケーションウィザードで作成された _tmain関数がある実装ファイルに以下のように記述してください。

// testSort.cpp : コンソールアプリケーションのエントリポイントを定義します。
//
#include "stdafx.h"

#include "MyObject.h"  //追加
#include "SortArray.h" //追加

#include "testSort.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

// 唯一のアプリケーションオブジェクトです。
CWinApp theApp;

using namespace std; 

void testSortArray();

//メイン関数
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) 
{
    //・
    //・

    if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0)) 
    {
        //・
        //・
    }
    else
    {
        testSortArray();
    }

    return nRetCode; 
}

void testSortArray()
{
    ::srand((unsigned int)time(NULL)); 

    CSortArray sortarray; 

    //CSortArrayにCMyObjectへのポインタを加える
    for (int i=0; i<10; i++) 
        sortarray.Add(new CMyObject); 

    //並び替え前の値を表示
    _tprintf(_T("before sort :"));
    for (int i=0; i<sortarray.GetCount(); i++) 
    {
        CMyObject *pMyObj = reinterpret_cast<CMyObject *>(sortarray.GetAt(i));
        _tprintf(_T(" %d"), pMyObj->GetValue());
    }
    _tprintf(_T("\n"));

    //並び替え
    sortarray.Sort();

    //並び替えた後の値表示
    _tprintf(_T("after sort :"));
    for (int i=0; i<sortarray.GetCount(); i++) 
    {
        CMyObject *pMyObj = reinterpret_cast<CMyObject *>(sortarray.GetAt(i));
        _tprintf(_T(" %d"), pMyObj->GetValue());
    }

    //後始末
    for (int i=0; i<sortarray.GetCount(); i++) 
        delete sortarray[i]; 
}

実行結果は以下のようになるかと思います。