{ -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座標は降順に並べ替えるにはどうしたらいいですか?
教えてください
Re: 教えてください
「x座標の昇順」を優先するのか「y座標の降順」を優先するのかに依って、回答が変わりそうな気がしますね。
これらの座標が{x座標,y座標}だとした場合、例えば、
{ -1, -2 }
{ 0,0 }
はどういう扱いになるのかという事ですね。
「x座標の昇順」を優先するならば、
{ -1, -2 }
{ 0,0 }
という並びになりそうですし、「y座標の降順」を優先するならば、
{ 0,0 }
{ -1, -2 }
という並びになりそうですね。
ただ、質問者様がやりたいことは、恐らく、優先順位の低い要素から優先順位の高い要素の順に安定的なソートを適用する事で解決可能に思えます。
これらの座標が{x座標,y座標}だとした場合、例えば、
{ -1, -2 }
{ 0,0 }
はどういう扱いになるのかという事ですね。
「x座標の昇順」を優先するならば、
{ -1, -2 }
{ 0,0 }
という並びになりそうですし、「y座標の降順」を優先するならば、
{ 0,0 }
{ -1, -2 }
という並びになりそうですね。
ただ、質問者様がやりたいことは、恐らく、優先順位の低い要素から優先順位の高い要素の順に安定的なソートを適用する事で解決可能に思えます。
Re: 教えてください
y座標を降順にソートした後、x座標を昇順にソートすれば良いと思います。
最初の「y座標を降順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。
しかし、「x座標を昇順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)
ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。
最初の「y座標を降順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。
しかし、「x座標を昇順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)
ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。
Re: 教えてください
訂正です。
全文書き直します。
---------
x座標を昇順にソートした後、y座標を降順にソートすれば良いと思います。
最初の「x座標を昇順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。
しかし、「y座標を降順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)
ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。
Re: 教えてください
全文書き直します。
---------
x座標を昇順にソートした後、y座標を降順にソートすれば良いと思います。
最初の「x座標を昇順にソート」の部分では安定的ではないソート(例えば、標準的なクイックソート等)でも構いません。
しかし、「y座標を降順にソート」の部分のソートには必ず安定的なソートを適用して下さい。(例:標準的なマージソート等)
ただ、私だったら、汎用性を取って、システム資源等に特段制約が無い限り、両者共に安定的なソートを実装します。
Re: 教えてください
Re: 教えてください
イメージして貰い易くする為に、最初の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: 教えてください
二つの要素でソートを行うからと言って2回ソートする必要はないでしょう。
一般に、ソートは比較関数を作るだけで実行可能です。その比較関数で二つの要素を比較すればいいわけです。
x,yの優先度を変える場合はcomp()関数のx,yを交換する。
昇順/降順を変えるにはreturn 1;/return -1;を反対にすればよい。
ソートアルゴリズムはクイックソートを使用していますが、ほかのアルゴリズムでも考えは一緒です。
一般に、ソートは比較関数を作るだけで実行可能です。その比較関数で二つの要素を比較すればいいわけです。
#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;
}
昇順/降順を変えるにはreturn 1;/return -1;を反対にすればよい。
ソートアルゴリズムはクイックソートを使用していますが、ほかのアルゴリズムでも考えは一緒です。