4

私は 2 次元配列を持っており、C++ で指定された qsort() 関数を使用してクイックソートしたいと考えています。

unsigned work[N][3];

work[i]「work」配列を3 番目のインデックスで並べ替えたいと思いwork[j]ますwork[i][2]>work[j][2]。

関数を使用して比較する必要があることはわかっていますが、それを行う方法がわかりません。

編集： 私が次のことをした場合、それは助けになりますか：

unsigned work[3][N];
qsort(work[2], N, sizeof(unsigned), compare);

そして、比較は次のようになります。

int compare(const void* a, const void* b)
{
    return(*(unsigned*)a-*(unsigned*)b);
}

?

4

2 に答える 2

4

まあ、簡単な答えは、まったく使用std::qsortしないことですが、std::sort. 残念ながら、後者はunsigned int[3]割り当て可能ではないため、機能しません。そこで、これが最も簡単なstd::qsort解決策です。

まず、カスタム コンパレータ関数を定義します。

// return -1 if a before b, 1 if after, 0 if equal
int compare(const void *a, const void *b)
{
    const unsigned int *arg1 = reinterpret_cast<const unsigned int*>(a);
    const unsigned int *arg2 = reinterpret_cast<const unsigned int*>(b);
    if(arg1[2] > arg2[2])
        return -1;
    if(arg1[2] < arg2[2])
        return 1;
    return 0;
}

次に、これを使用して配列をソートします。workこれは配列の配列であり、したがってwork[0]3 の配列であることに注意してくださいunsigned int。ポインタの間接化はまったく関係ありません。したがって、次のように並べ替えるのに最適ですstd::qsort。

std::qsort(work, sizeof(work)/sizeof(work[0]), sizeof(work[0]), compare);

ちなみに、C++ (および他の多くのプログラミング言語) では2通常 でカウントを開始するため、3 番目の要素は でインデックス付けされます。0

編集:std::vectorただし、実際には、この配列の配列を削除し、 of std::array<unsigned int,3>s (または実際のコンテキストにもう少し適合する他のデータ構造) のような C++ に適したものを使用するのが最善の解決策です。

typedef std::array<unsigned int,3> uint3;
std::vector<uint3> work(N);

次に、単純な方法でソートできます。

std::sort(std::begin(work), std::end(work), 
          [](const uint3 &a, const uint3 &b) { return a[2] > b[2]; });

または、C++11 を持っていない場合 (ただし、この場合はstd::arrayどちらも持っていないため、単なる 3 配列とは別に、適切なデータ構造について考え始める必要があります):

struct compare
{
    bool operator()(const uint3 &a, const uint3 &b) const
    {
        return a[2] > b[2];
    }
};

std::sort(work.begin(), work.end(), compare());

より明確なコードへのボーナスとして、ほとんどの場合、パフォーマンスがわずかに向上std::sortしstd::qsortます。

于 2013-01-10T09:23:28.467 に答える
2

はい、できますqsort()。qsort()必要な「もの」の線形ブロックを取得し、サイズ（バイト単位）を指定する均一なサイズのチャンクに分割し、比較のために各ブロックパーティションのベースアドレスを提供することで機能します。

まず、必要なサイズを決定します。ソートしている「もの」は、3 要素幅の配列行であることは明らかです。次に、ポインターなどの 2 つのもののベース アドレスを受け入れることができるコンパレーターを作成します。この場合、単純なポインターが機能します。最後に、実際の比較は、与えられp[2]た各ポインターから 3 つの要素の深さ (正確には) になります。p

それでは、コードを肉付けしましょう：

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

static const size_t ROWSIZE = 3;

static void print_array(int rows, int ar[rows][ROWSIZE])
{
    int i,j;
    for (i=0;i<rows;++i)
    {
        for (j=0; j<ROWSIZE; printf("%d ", ar[i][j++]));
        printf("\n");
    }
    printf("\n");
}

// compare function
static int compare_row(const void* left, const void* right)
{
    const int *ileft = left, *iright = right;
    return ileft[ROWSIZE-1] - iright[ROWSIZE-1];
}

int main()
{
    int ar[10][ROWSIZE] = {0}, i;

    // fill with random junk from 10 to 99
    srand((unsigned)time(0));

    for (i=0;i<ROWSIZE * sizeof(ar)/sizeof(ar[0]); ++i)
        ar[i/ROWSIZE][i%ROWSIZE] = 10 + (rand() % 90);

    // print prior to sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);

    // send to qsort
    qsort(ar, sizeof(ar)/sizeof(ar[0]), sizeof(ar[0]), compare_row);

    // print again after sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);

    return EXIT_SUCCESS;
}

サンプル出力

50 14 23 
69 81 93 
30 72 18 
26 49 29 
51 87 58 
18 74 40 
26 61 26 
43 80 27 
27 61 34 
13 66 89 

30 72 18 
50 14 23 
26 61 26 
43 80 27 
26 49 29 
27 61 34 
18 74 40 
51 87 58 
13 66 89 
69 81 93
于 2013-01-10T09:44:02.923 に答える