c++ - 特定のセルで 2 次元配列をクイックソートするにはどうすればよいですか?

Question

私は 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);
}

?

score 4 · Accepted Answer

まあ、簡単な答えは、まったく使用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ます。

score 2 · Accepted Answer

はい、できます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;
}

サンプル出力

c++ - 特定のセルで 2 次元配列をクイックソートするにはどうすればよいですか?

2 に答える 2

Related

Reference