配列を値でランク付け (ソート) するにはどうすればよいでしょうか?*ひねりを加えて*
質問
を使用して配列を昇順に並べ替えたいと考えています C/C++
. 。結果は要素インデックスを含む配列になります。各インデックスは、ソートされた配列内の要素の位置に対応します。
例
Input: 1, 3, 4, 9, 6
Output: 1, 2, 3, 5, 4
編集: シェルソートプロシージャを使用しています。重複値のインデックスは、どの重複値が元の配列の最初にあるかに基づいて任意に選択されます。
アップデート:
最善の努力にもかかわらず、ポインターの配列の並べ替えアルゴリズムを実装できませんでした。現在の例はコンパイルできません。
誰か、何が問題なのか教えてもらえますか?
助けていただければ幸いです。
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]; //the problem lies somewhere in here
&pArray[j + 1] = &temp;
flag = 1; // indicates that a swap occurred.
}
}
}
};
解決
C++ を使用しているので、次のようにします。の SortIntPointers
関数には任意の並べ替えアルゴリズムを使用できますが、重要なのは、関数が次の基準に基づいてポインターの配列を並べ替えることです。 int
彼らが指していること。それが完了したら、ポインターの配列を調べて、元の配列の元の位置に配置されるソートされたインデックスを割り当てることができます。
int* intArray; // set somewhere else
int arrayLen; // set somewhere else
int** pintArray = new int*[arrayLen];
for(int i = 0; i < arrayLen; ++i)
{
pintArray[i] = &intArray[i];
}
// This function sorts the pointers according to the values they
// point to. In effect, it sorts intArray without losing the positional
// information.
SortIntPointers(pintArray, arrayLen);
// Dereference the pointers and assign their sorted position.
for(int i = 0; i < arrayLen; ++i)
{
*pintArray[i] = i;
}
それが十分明らかであれば幸いです。
他のヒント
OK、これが C++ での私の試みです
#include <iostream>
#include <algorithm>
struct mycomparison
{
bool operator() (int* lhs, int* rhs) {return (*lhs) < (*rhs);}
};
int main(int argc, char* argv[])
{
int myarray[] = {1, 3, 6, 2, 4, 9, 5, 12, 10};
const size_t size = sizeof(myarray) / sizeof(myarray[0]);
int *arrayofpointers[size];
for(int i = 0; i < size; ++i)
{
arrayofpointers[i] = myarray + i;
}
std::sort(arrayofpointers, arrayofpointers + size, mycomparison());
for(int i = 0; i < size; ++i)
{
*arrayofpointers[i] = i + 1;
}
for(int i = 0; i < size; ++i)
{
std::cout << myarray[i] << " ";
}
std::cout << std::endl;
return 0;
}
0 から n-1 まで増加する値を持つ新しい配列を作成します (n は並べ替える配列の長さです)。次に、新しい配列の値によってインデックス付けされた古い配列の値に基づいて、新しい配列を並べ替えます。
たとえば、バブル ソートを使用する場合 (説明が簡単です)、新しい配列の値を比較する代わりに、新しい配列の値によってインデックス付けされた位置で古い配列の値を比較します。
function bubbleRank(A){
var B = new Array();
for(var i=0; i<A.length; i++){
B[i] = i;
}
do{
swapped = false;
for(var i=0; i<A.length; i++){
if(A[B[i]] > A[B[i+1]]){
var temp = B[i];
B[i] = B[i+1];
B[i+1] = temp;
swapped = true;
}
}
}while(swapped);
return B;
}
そうですね、自明な n^2 解があります。
Python の場合:
newArray = sorted(oldArray)
blankArray = [0] * len(oldArray)
for i in xrange(len(newArray)):
dex = oldArray.index(newArray[i])
blankArray[dex] = i
リストの大きさによっては、これが機能する場合があります。リストが非常に長い場合は、奇妙な並列配列ソートを実行する必要がありますが、これはあまり面白くなく、コードに余分なバグを簡単に導入する方法です。
また、上記のコードは、oldArray 内の一意の値を想定していることにも注意してください。そうでない場合は、結合された値を解決するために後処理を行う必要があります。
boost::lambda を使用したベクトルの並列ソート...
std::vector<int> intVector;
std::vector<int> rank;
// set up values according to your example...
intVector.push_back( 1 );
intVector.push_back( 3 );
intVector.push_back( 4 );
intVector.push_back( 9 );
intVector.push_back( 6 );
for( int i = 0; i < intVector.size(); ++i )
{
rank.push_back( i );
}
using namespace boost::lambda;
std::sort(
rank.begin(), rank.end(),
var( intVector )[ _1 ] < var( intVector )[ _2 ]
);
//... and because you wanted to replace the values of the original with
// their rank
intVector = rank;
注記:より明確で簡単なため、配列の代わりに VectorS を使用しました。また、1 ではなく 0 からカウントを開始する C スタイルのインデックスを使用しました。
新しい配列を作成し、バブルソートを使用して要素をランク付けします
int arr[n];
int rank[n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(arr[i]>arr[j])
rank[i]++;
各要素のランクは、rank[i]+1 となり、1、2、...n の順になります。
これはC言語での解決策です
#include <stdio.h>
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++)
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
/* Function to print an array */
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 98};
int arr_original[] = {64, 34, 25, 12, 22, 11, 98};
int rank[7];
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
//PLACE RANK
//look for location of number in original array
//place the location in rank array
int counter = 1;
for (int k = 0; k < n; k++){
for (int i = 0; i < n; i++){
printf("Checking..%d\n", i);
if (arr_original[i] == arr[k]){
rank[i] = counter;
counter++;
printf("Found..%d\n", i);
}
}
}
printf("Original array: \n");
printArray(arr_original, n);
printf("Rank array: \n");
printArray(rank, n);
return 0;
}