4

私が作成したソート方法について少しアドバイスをいただければ幸いです。

このコードの目的は、int ポインター配列を作成し、その配列内のポインターを通常の int 配列の内容でソートすることです。次に、元の int 配列の場所に基づいて別の変数に値を割り当てます。

このコードで私が経験している奇妙な点は、私が知る限り何の影響も与えないはずのテスト コードが、実際にはポインターの内容に影響を与えていることです。おそらく値は変わっていませんが、テスト コードの書き方が原因でエラーが発生しています。

 //create array
 int c[8] = {3,1,5,7,8,2,6,4};
 //create pointer array
 int *newptr[8];
 for(int k = 0; k<8; k++)
 {
     newptr[k] = &c[k];
 }
//sort pointer array
for(int j = 0; j<8; j++)
{
    for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
    {
        int *temp = newptr[j+1];
        newptr[j+1] = newptr[j];
        newptr[j] = temp;
    }
}
//set lookuplocation
int lookuplocation;
for(int i = 0; i<8; i++)
{
    cout << *newptr[i];

    if(newptr[i] == &c[0])
    {
        cout << *newptr[i] << endl;

        //If I use endl or \n to test the pointers values I end up with only
        //a part of the correct data. 

        cout << "\nSuccess!\n";
        lookuplocation = 0;
    }
}
//Also for my last test sometimes the first element gets messed up as well
//test arrays
for(int k = 0; k<8; k++)
{
    cout << "Element " << k << ": " << *newptr[k] << endl;
    cout << "Element " << k << ": " << newptr[k] << endl;
}
4

5 に答える 5

3

配列c[n]の範囲が [1 .. n ] の場合、O( n ) 時間の複雑さで機能する次のアルゴリズムを使用できます。

for(int j = 0; j < n; j++)
    while(*newptr[*newptr[j] - 1] != *newptr[j])
        std::swap(newptr[*newptr[j] - 1], newptr[j]);

その背後にある考え方は、値 1 をポインターnewptr[0]に、2 をポインターnewptr[1]に、...、およびnをポインターに割り当てることnewptr[n-1]です。より効率的なアルゴリズムはありません (特に C++11 では、std::swapが使用されるためstd::move)。

の場合int c[8] = {3,1,5,7,8,2,6,4}、次のようになります (値テーブルへの参照は無視します)。

1233

成功！
45678

更新：逆の順序が必要な場合：

for(int j = 0; j < n; j++)
    while(*newptr[n - *newptr[j]] != *newptr[j])
        std::swap(newptr[n - *newptr[j]], newptr[j]);

の場合int c[8] = {3,1,5,7,8,2,6,4}、次のようになります。

8765433

成功！
21

于 2013-08-05T08:07:13.767 に答える
1

一般的なアプローチは、指定さsortれたコンパレータで要素をソートする汎用関数を実装することです。これにより、配列要素を抽象化できます。いくつかの方法があります:

template<typename ElementType, typename CompType>
void sort(ElementType array[], size_t size, CompType cmp);
template<typename ElementType, typename CompType>
void sort(std::vector<ElementType> & array, CompType cmp);
template<typename IteratorType, typename CompType>
void sort(IteratorType first, IteratorType last, CompType cmp);

コンテナタイプも抽象化できるため、最後の方法が望ましいです。

于 2013-08-05T11:36:10.477 に答える