|
|
Microsoft Visual Studio .NET 2003 |
| ■ソート |
Prev Top Next 関連ページ：なし |
ソートのアルゴリズムのひとつであるマージソートを紹介します。まあ紹介といってもネット上で調べたことをもとにしているので マージソートの詳細については下記のサイトを参照してください。
---SORT.h---
#ifndef SORT_H
#define SORT_H
//３次元頂点座標の定義
typedef struct _VECTOR3
{
float x;
float y;
float z;
struct _VECTOR3* next;
}VECTOR3;
//ソートモードの定義
enum SORTMODE
{
SORTMODE_ASC = 0, //昇順
SORTMODE_DESC = 1, //降順
};
class SORT
{
private:
VECTOR3* m_VectorTop; //先頭のアドレス
VECTOR3* m_Vector; //リスト構造
VECTOR3* m_VectorSearch; //検索用ポインタ
long m_VectorCnt; //リスト構造の要素数
SORTMODE m_SortMode; //ソートのモード
private:
VECTOR3* MergeDecomposition( VECTOR3* pVector, long ArrayCnt );
VECTOR3* Merge( VECTOR3* pV1, VECTOR3* pV2 );
public:
SORT();
~SORT();
//頂点座標を追加
void AddVector( float x, float y, float z );
//頂点座標を追加
void AddVector( VECTOR3* pVector );
//頂点要素を全削除
void AllClearVector();
//検索用ポインタを先頭にする
void MoveTop();
//検索用ポインタを１つ進める
void MoveNext();
//検索用ポインタが終端か
bool Eof();
//検索中の要素のポインタを取得
VECTOR3* GetVector(){ return m_VectorSearch; };
//要素数を取得
long GetCount(){ return m_VectorCnt; };
//マージソート
void MergeSort( SORTMODE SortMode );
};
#endif
SORTクラスは３次元頂点座標をリスト構造で保持するクラスです。データとして３次元頂点座標しか保持してないのでDirect3Dで実践的に使用できるクラスではないです。まあサンプルなんでこれで勘弁。
---SORT.cpp---
#include "SORT.h"
SORT::SORT()
{
m_VectorTop = NULL;
m_Vector = NULL;
m_VectorSearch = NULL;
m_VectorCnt = 0;
}
SORT::~SORT()
{
AllClearVector();
}
void SORT::AddVector( float x, float y, float z )
{
m_VectorCnt++;
VECTOR3* pVector = new VECTOR3;
pVector->x = x;
pVector->y = y;
pVector->z = z;
pVector->next = NULL;
if( m_VectorTop != NULL )
{
//領域拡張前のリストの最後に作成したデータのポインタをつなげる
VECTOR3* v = m_VectorTop;
while( 1 )
{
if( v->next == NULL )
{
v->next = pVector;
break;
}
v = v->next;
}
}
//ヘッダにまだ設定してないときは設定する
else
{
m_VectorTop = pVector;
m_Vector = pVector;
}
}
void SORT::AddVector( VECTOR3* pVector )
{
AddVector( pVector->x, pVector->y, pVector->z );
}
//リスト構造内のデータを全削除
void SORT::AllClearVector()
{
VECTOR3* v = m_VectorTop;
while( v != NULL )
{
VECTOR3* vbk = v->next;
delete v;
v = vbk;
}
m_VectorTop = NULL;
m_Vector = NULL;
m_VectorSearch = NULL;
m_VectorCnt = 0;
}
void SORT::MoveTop()
{
m_VectorSearch = m_VectorTop;
}
void SORT::MoveNext()
{
m_VectorSearch = m_VectorSearch->next;
}
bool SORT::Eof()
{
if( m_VectorTop == NULL || m_Vector == NULL || m_VectorSearch == NULL )
return true;
return false;
}
//マージソード
void SORT::MergeSort( SORTMODE SortMode )
{
m_SortMode = SortMode;
m_VectorTop = MergeDecomposition( m_VectorTop, m_VectorCnt );
}
//再帰的に分解していく。最終的に２要素まで分解し、それをソートして連結していく
VECTOR3* SORT::MergeDecomposition( VECTOR3* pVector, long ArrayCnt )
{
VECTOR3 *pV1, *pV2;
//要素数が1以下のときは何もしない
if( ArrayCnt <= 1 )
return pVector;
pV1 = pVector;
//半分までポインタを移動させる。
int h = ArrayCnt / 2 - 1;
for( int i=0; i<h; i++ )
pV1 = pV1->next;
//後半部分の先頭ポインタをセット
pV2 = pV1->next;
//前半部分の終了ポインタをセット
pV1->next = NULL;
//再帰的に分割していき、最終的に結合する
return Merge( MergeDecomposition( pVector, ArrayCnt / 2 ), MergeDecomposition( pV2, ArrayCnt - ArrayCnt / 2 ) );
}
//pV1とpV2を1要素ずつ比較していき次々に連結していく
VECTOR3* SORT::Merge( VECTOR3* pV1, VECTOR3* pV2 )
{
//連結後のリスト
VECTOR3 list, *p;
p = &list;
//分割されている２つのリストの要素をソートしていく
while( pV1 != NULL && pV2 != NULL )
{
switch( m_SortMode )
{
//降順モード
case SORTMODE_DESC:
if( pV1->z <= pV2->z )
{
//大きい方の要素をマージ後のリストに連結する
p->next = pV2;
//連結した方のリストのポインタを進める
pV2 = pV2->next;
//連結後のリストのポインタを進める
p = p->next;
}
else
{
//大きい方の要素をマージ後のリストに連結する
p->next = pV1;
//連結した方のリストのポインタを進める
pV1 = pV1->next;
//連結後のリストのポインタを進める
p = p->next;
}
break;
//昇順モード
case SORTMODE_ASC:
//小さい方の要素をマージ後のリストに連結する
if( pV1->z <= pV2->z )
{
//大きい方の要素をマージ後のリストに連結する
p->next = pV1;
//連結した方のリストのポインタを進める
pV1 = pV1->next;
//連結後のリストのポインタを進める
p = p->next;
}
else
{
//大きい方の要素をマージ後のリストに連結する
p->next = pV2;
//連結した方のリストのポインタを進める
pV2 = pV2->next;
//連結後のリストのポインタを進める
p = p->next;
}
break;
default:
break;
}
}
//片方のリストが先に空になるので残りを連結する
if( pV1 == NULL )
p->next = pV2;
else
p->next = pV1;
//p->nextに連結していくのでlist.nextをかえす
return list.next;
}
---main.cpp---
//〜〜〜いろいろ省略〜〜〜
//乱数ジェネレータを初期化
srand((unsigned)time( NULL ));
SORT SortCls;
//要素数１８で適当に頂点座標をセット
int cnt = 18;
for( int i=0; i<cnt; i++ )
SortCls.AddVector( (float)(rand()%100), (float)(rand()%100), (float)(rand()%100) );
char str[256];
cnt = 0;
//検索前にポインタを先頭に移動する
SortCls.MoveTop();
FILE* f = NULL;
f = fopen( "ソート前.txt", "w" );
while( !SortCls.Eof() )
{
//ソート前の３次元頂点座標のz値をテキストファイルに出力
sprintf( str, "%02d : %f\n", cnt, SortCls.GetVector()->z );
fputs( str, f );
cnt++;
//次のポインタへ移動
SortCls.MoveNext();
}
fclose( f );
//マージソートを降順で実行
SortCls.MergeSort( SORTMODE_DESC );
cnt = 0;
//検索前にポインタを先頭に移動する
SortCls.MoveTop();
f = NULL;
f = fopen( "ソート後.txt", "w" );
while( !SortCls.Eof() )
{
//ソート後の３次元頂点座標のz値をテキストファイルに出力
sprintf( str, "%02d : %f\n", cnt, SortCls.GetVector()->z );
fputs( str, f );
cnt++;
//次のポインタへ移動
SortCls.MoveNext();
}
fclose( f );
//〜〜〜いろいろ省略〜〜〜
main.cppは必要な部分のみ書いています。SORTクラスを要素数１８で初期化し、次にソート前とソート後の３次元頂点座標のz値をテキストファイルに出力しています。
さてこの面倒くさいソートですが、ゲーム制作で実際にどういう目的で使用するのかというと、ぶっちゃけあんまり使用しないと思います。アイテムの表示順を並べ替えたりとかそんなところくらいではないでしょうか。 半透明オブジェクトをZバッファ法により陰面処理する際、半透明オブジェクトの表示位置によりソートすることもありますが、この辺についてはあとで検証してみることにします。
最後にソースコードに間違いがあったらご指摘ください。勘違いしてる可能性があるので。あとエラーチェックやってなかったり、要素の一部のみ削除する機能がなかったり中途半端なのでその辺は修正してください。