1

2*n 行列をソートしたいのですが、入力で n が指定されています。行列を出力するプログラムを作成してください。要件は次のとおりです。

  1. 最初の列は ASC でソートする必要があり、
  2. 可能であれば、DESC の 2 列目。

たとえば、n = 5 とすると、行列は次のようになります。

3 4
1 2
3 5
1 6
7 3

結果は

1 6
1 2
3 5
3 4
7 3

というわけで、こんな感じでコードを書きます。最初の行に値 n を入力し、次の行は上記と同様です。

#include <stdio.h>
#define TWO_16 65536
#define TWO_15 32768

int v[100000][2];
int z[100000];
int vec[100000];
int n;


int main()
{
    int i, j;
    scanf ("%d", &n);   // give the value of n;
    for (i = 1; i <= n; i++)    // filling the matrix;
    {
        scanf ("%d%d", &v[i][0], &v[i][1]);
        z[i] = TWO_16 * v[i][0] + TWO_15 - v[i][1];
        vec[i] = i;
    }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
        {
            if (z[j] > z[i])
            {
                int t = vec[i];
                vec[i] = vec[j];
                vec[j] = t;
            }
        }

    for (i = 1; i <= n; i++)   // output the matrix
        printf("%d %d\n",v[vec[i]][0],v[vec[i]][1]);
    return 0;
}

しかしgccでは、出力は

1 6
3 5
3 4
1 2
7 3

さらに、入力で1行目を「1 2」に変更し、2行目を「3 4」に変更すると、結果も変わりました。

私のコードの問題は何ですか？

追加情報：

z[]この問題の要件を満たす関数を使用しているため、使用しているため、単純に並べ替えることができます。vec[]配列の移動には多くの時間がかかる可能性があるため、元のインデックスを保存します。つまりv[vec[i]][0]、「新しい」配列の item を意味しますi。v[0] は使用されないことに注意してください。n が 100000 未満で、等しくありません。

4

2 に答える 2

2

に格納されている値を比較していますz[]が、 の要素を交換していvecます。したがって、最初は次のようになります。

i  vec      z
------------------
1   1     z[1]
2   2     z[2]
3   3     z[3]
...

たとえば、2 を 3 に交換した後

i  vec      z
------------------
1   1     z[1]
2   3     z[2]
3   2     z[3]
...

と の間のマッピングが不適切にvecなりzます。

したがって、別の反復では、 と再度比較z[2]しz[3]、 の要素を交換する必要がありますvec。そのため、少なくとも z の要素を交換しzたり、 z の要素を次の要素を使用してインデックスしたりする必要があります。vec

i  vec      z
------------------
1   1    z[vec[1]] = z[1]
2   3    z[vec[2]] = z[3]
3   2    z[vec[3]] = z[2]
...

これを追加するとうまくいくはずです

...
int t = vec[i];
vec[i] = vec[j];
vec[j] = t;
//Add this also when swapping vec
t = z[i];
z[i] = z[j];
z[j] = t;
...
于 2013-10-03T10:49:48.273 に答える
2

配列インデックスは 0 から始まるため、for cicles は 0 から開始する必要があります

if (z[j] > z[i]): 並べ替えたいvのに、比較zして並べ替えていますvec。ソートvecと比較によるzバブルソートは機能しません。同じ配列を使用する必要があります。

于 2013-10-03T09:27:53.703 に答える