5

を使用して配列を昇順にソートしたいと思います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.
            }
        }
    }
};
4

7 に答える 7

7

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;
}

うまくいけば、それは十分に明確です。

于 2008-08-17T02:33:32.687 に答える
3

わかりました、これが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;
}
于 2008-09-23T07:30:30.587 に答える
2

値が 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;
}
于 2008-08-17T02:46:22.833 に答える
1

新しい配列を作成し、バブルソートを使用して要素をランク付けします

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 の順になります。

于 2015-10-18T06:21:35.523 に答える
0

さて、簡単な n^2 ソリューションがあります。

パイソンでは：

newArray = sorted(oldArray)
blankArray = [0] * len(oldArray)
for i in xrange(len(newArray)):
  dex = oldArray.index(newArray[i])
  blankArray[dex]  = i

リストの大きさによっては、これでうまくいく場合があります。リストが非常に長い場合、奇妙な並列配列ソートを行う必要がありますが、これはあまり楽しくないように見え、コードに余分なバグを導入する簡単な方法です。

また、上記のコードは、oldArray で一意の値を想定していることにも注意してください。そうでない場合は、同点の値を解決するために何らかの後処理を行う必要があります。

于 2008-08-17T02:21:28.563 に答える
0

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 スタイルのインデックスを使用しました。

于 2008-09-23T16:23:01.290 に答える