教えてください

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 教えてください

Re: 教えてください

#8

by maru » 8年前

二つの要素でソートを行うからと言って２回ソートする必要はないでしょう。
一般に、ソートは比較関数を作るだけで実行可能です。その比較関数で二つの要素を比較すればいいわけです。

コード: 

#include <stdio.h>
#include <stdlib.h>

typedef struct tagElement
{	double x;
	double y;
} Element;

/*データ*/
Element	Elements[] =
{	{ -1, -2 }, { -0.99,0 }, { 0,0 }, { -3.1,+5.1 }, { -6,+6 }, { -3,-3 }, { -3.5,-3.1 },
	{ 0,+0.5 }, { -0.99,+0.5 }, { -3,-2 }, { -3.61, -1e10 }, { -3, +2 }, { -0.99, +1.5 }, { -2.4, -2 },
	{ -3.6, -3 }, { -3.5, -3 }, { -1.0, +1.5 }, { -1, -1 }, { -5.4, +5.2 },
};

/* 比較関数 */
int comp(const void* a, const void* b)
{	Element*	p1 = (Element*)a;
	Element*	p2 = (Element*)b;
	/*y要素で比較*/
	if (p1->y < p2->y)		{	return 1;	}
	else if (p1->y > p2->y)	{	return -1;	}
	else
	{	/* x要素で比較 */
		if (p1->x < p2->x)		{	return -1;	}
		else if (p1->x > p2->x)	{	return 1;	}
	}
	return 0;	/*完全に一致する場合は0を返す*/
}

int main()
{	size_t	numberOfElements = sizeof(Elements) / sizeof(Element);
	Element*	p = Elements;
	qsort(p, numberOfElements, sizeof(Element), comp);
	for (size_t i = 0; i < numberOfElements; ++i, ++p)
	{	printf("{%f,%f}\n", p->x, p->y);
	}
	return 0;
}
x,yの優先度を変える場合はcomp()関数のx,ｙを交換する。
昇順/降順を変えるにはreturn 1;/return -1；を反対にすればよい。

ソートアルゴリズムはクイックソートを使用していますが、ほかのアルゴリズムでも考えは一緒です。

Re: 教えてください

#7

by 白い変人 » 8年前

イメージして貰い易くする為に、最初の3座標だけをソートする即席のサンプルコードを作ってみましてので、軽く読んでみて、大まかな流れを理解してみて下さい。

因みに、使われている安定的なソートは、非効率的と言われているバブルソートです。

コード: 

#include <stdio.h>

typedef struct ELEMENT{
	double x;
	double y;
}ELEMENT;

//x座標を昇順にソート
int ascending_sort(ELEMENT *array,int size){
	char flag;
	int i,j;
	ELEMENT work;
	
	if(size<=0) return 1;
	
	for(i=0;i<size-1;i++){
		flag=0;
		
		for(j=size-1;j>i;j--){
			if(array[j-1].x>array[j].x){
				work=array[j];
				array[j]=array[j-1];
				array[j-1]=work;
				flag=1;
			}
		}
		
		if(flag==0) break;
	}
	
	return 0;
}

//y座標を降順にソート
int descending_sort(ELEMENT *array,int size){
	char flag;
	int i,j;
	ELEMENT work;
	
	if(size<=0) return 1;
	
	for(i=0;i<size-1;i++){
		flag=0;
		
		for(j=size-1;j>i;j--){
			if(array[j-1].y<array[j].y){
				work=array[j];
				array[j]=array[j-1];
				array[j-1]=work;
				flag=1;
			}
		}
		
		if(flag==0) break;
	}
	
	return 0;
}

int main(void){
	ELEMENT array[3];
	
	int i;
	
	//配列の初期化
	for(i=0;i<3;i++){
		array[i].x=0;
		array[i].y=0;
	}
	
	//データの入力
	array[0].x=-1;
	array[0].y=-2;
	
	array[1].x=-0.99f;
	array[1].y=0;
	
	array[2].x=0;
	array[2].y=0;
	
	//x座標を昇順にソート
	ascending_sort(array,3);
	
	//y座標を降順にソート
	descending_sort(array,3);
	
	//結果の表示
	for(i=0;i<3;i++) printf("{%f,%f}\n",array[i].x,array[i].y);
	
	return 0;
}

Re: 教えてください

#6

by 白い変人 » 8年前

訂正です。

全文書き直します。

---------

x座標を昇順にソートした後、y座標を降順にソートすれば良いと思います。

最初の「x座標を昇順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。

しかし、「y座標を降順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)

ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。
Re: 教えてください

Re: 教えてください

#5

by 白い変人 » 8年前

y座標を降順にソートした後、x座標を昇順にソートすれば良いと思います。

最初の「y座標を降順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。

しかし、「x座標を昇順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)

ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。

Re: 教えてください

#4

by つい » 8年前

ｙ座標優先だとどうなりますか？

Re: 教えてください

#3

by 白い変人 » 8年前

「x座標の昇順」を優先するのか「y座標の降順」を優先するのかに依って、回答が変わりそうな気がしますね。

これらの座標が{x座標,y座標}だとした場合、例えば、

{ -1, -2 }
{ 0,0 }

はどういう扱いになるのかという事ですね。

「x座標の昇順」を優先するならば、

{ -1, -2 }
{ 0,0 }

という並びになりそうですし、「y座標の降順」を優先するならば、

{ 0,0 }
{ -1, -2 }

という並びになりそうですね。

ただ、質問者様がやりたいことは、恐らく、優先順位の低い要素から優先順位の高い要素の順に安定的なソートを適用する事で解決可能に思えます。

Re: 教えてください

#2

by box » 8年前

どういう結果がほしいのですか？
例題の座標群で提示してください。

教えてください

#1

by つい » 8年前

{ -1, -2 },{ -0.99,0 },{ 0,0 },{ -3.1,+5.1 },{ -6,+6 },{ -3,-3 },{ -3.5,-3.1 },
{ 0,+0.5 },{ -0.99,+0.5 },{ -3,-2 },{ -3.61, -1e10 },{ -3, +2 },{ -0.99, +1.5 },{ -2.4, -2 },
{ -3.6, -3 },{ -3.5, -3 },{ -1.0, +1.5 },{ -1, -1 },{ -5.4, +5.2 },

これらの座標をx座標は昇順、y座標は降順に並べ替えるにはどうしたらいいですか？

ページトップ