double ポインターの配列を、それらが指す値に基づいて並べ替えるにはどうすればよいですか?
質問
C/C++で配列をソートし、各値をその「スコア」またはランクに置き換える関数を構築しようとしています。これは、int の配列への double ポインタ配列を受け取り、整数の逆参照値に基づいて double ポインタを並べ替えます。何度も試してみましたが、うまくいきません。もう一度言いますが、ダブル ポインターが指す値に基づいてダブル ポインターを並べ替える必要があります。これが私が持っているものです:
void SortArray( int ** pArray, int ArrayLength )
{
int i, j, flag = 1; // set flag to 1 to begin initial pass
int * temp; // holding variable orig with no *
for(i = 1; (i <= ArrayLength) && flag; i++)
{
flag = 0;
for (j = 0; j < (ArrayLength -1); j++)
{
if (*pArray[j+1] > *pArray[j]) // ascending order simply changes to <
{
temp = &pArray[j]; // swap elements
pArray[j] = &pArray[j+1];
pArray[j+1] = &temp;
flag = 1; // indicates that a swap occurred.
}
}
}
}
解決
もうすぐですよ。スワップ時に配列項目のアドレスを参照していますが、これは必要ありません。配列内の項目はポインターなので、それを交換する必要があります。
以下を参照してください:
void SortArray( int ** pArray, int ArrayLength )
{
int i, j, flag = 1; // set flag to 1 to begin initial pass
int * temp; // holding variable orig with no *
for(i = ArrayLength - 1; i > 0 && flag; i--)
{
flag = 0;
for (j = 0; j < i; j++)
{
if (*pArray[j] > *pArray[j+1]) // ascending order simply changes to <
{
temp = pArray[j]; // swap elements
pArray[j] = pArray[j+1];
pArray[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
}
また、チェックしてください バブルソーティングに関するこの素敵なブログ投稿 興味があればどうぞ(ごめんなさい、恥知らずなプラグです:))。宿題のお役に立てば幸いです ;)
編集:配列の長さから逆算し、内側のループで 'i' までのみインクリメントする微妙な「最適化」に注目してください。これにより、すでに並べ替えられたアイテムを不必要に再解析する必要がなくなります。
他のヒント
へー、これは宿題じゃないよ。
その場合は、STL を使用して配列を管理し、並べ替えることを検討してください。開発と保守が簡単で、std::sort アルゴリズムはバブル ソートよりも漸近的に高速です。
使用を検討する必要があります std::swap()
交換を行うために。その場合は、次のように呼び出します。
swap( obj1, obj2 );
それよりも:
std::swap( obj1, obj2 );
最初の呼び出しセマンティクスにより、適切な名前空間検索が可能になり、正しいオーバーロードが存在する場合にはそれを見つけることができます。必ず次のいずれかを持っているようにしてください。
using namespace std;
または:
using std::swap;
どこかで。
うーん、私は STL の経験があまりありません。例を挙げていただけますか?
このプログラムは、int のベクトルを作成し、それを並べ替えて、結果を表示します。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector<int>; vec;
vec.push_back(7);
vec.push_back(5);
vec.push_back(13);
sort(vec.begin(), vec.end());
for (vector<int>::size_type i = 0; i < vec.size(); ++i)
{
cout << vec[i] << endl;
}
}
Brian Ensink の投稿を完成させるには、STL が驚きに満ちていることに気づくでしょう。たとえば、 std::sort アルゴリズムは次のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
void printArray(const std::vector<int *> & p_aInt)
{
for(std::vector<int *>::size_type i = 0, iMax = p_aInt.size(); i < iMax; ++i)
{
std::cout << "i[" << static_cast<int>(i) << "] = " << reinterpret_cast<unsigned int>(p_aInt[i]) << std::endl ;
}
std::cout << std::endl ;
}
int main(int argc, char **argv)
{
int a = 1 ;
int b = 2 ;
int c = 3 ;
int d = 4 ;
int e = 5 ;
std::vector<int *> aInt ;
// We fill the vector with variables in an unordered way
aInt.push_back(&c) ;
aInt.push_back(&b) ;
aInt.push_back(&e) ;
aInt.push_back(&d) ;
aInt.push_back(&a) ;
printArray(aInt) ; // We see the addresses are NOT ordered
std::sort(aInt.begin(), aInt.end()) ; // DO THE SORTING
printArray(aInt) ; // We see the addresses are ORDERED
return EXIT_SUCCESS;
}
配列の最初の出力では、順序付けられていないアドレスが表示されます。2 つ目は、ソート後、順序付けされたアドレスを表示します。私のコンパイラには次のものがあります。
i[0] = 3216087168
i[1] = 3216087172
i[2] = 3216087160
i[3] = 3216087164
i[4] = 3216087176
i[0] = 3216087160
i[1] = 3216087164
i[2] = 3216087168
i[3] = 3216087172
i[4] = 3216087176
STL の <algorithm> ヘッダーを見てください。 http://www.cplusplus.com/reference/algorithm/たくさんのユーティリティが見つかります。より適切なコンテナーの実装が他にもあることに注意してください (std::list?std::map?)。