0

1つのアイテムに基づいてリストを並べ替えることはできますか？

たとえば、私が持っている場合

1,3,2,4,5,6,7 ... 1000000

そして、それが2番目の要素であることを知っています。リスト全体を再ソートしなくても、その間の正しい位置に3効率的にソートすることは可能ですか？324

編集：このシナリオでは、リストの残りの部分がすでに並べ替えられていると想定されていることにも注意してください。今は場違いなのはそれだけ3です。

4

6 に答える 6

7

順序付けされていないオブジェクト（O（n））を見つけ、オブジェクトを取り出し（O（1））、正しい位置を見つけ（O（n））、もう一度挿入します（O（1））。

C ++ 11を想定すると、

#include <list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> values {1, 2, 3, 9, 4, 5, 6, 7, 12, 14};

    auto it = std::is_sorted_until(values.begin(), values.end());
    auto val = *--it;
    // ^ find that object.

    auto next = values.erase(it);
    // ^ remove it.

    auto ins = std::lower_bound(next, values.end(), val);
    // ^ find where to put it back.

    values.insert(ins, val);
    // ^ insert it.

    for (auto value : values) {
        std::cout << value << std::endl;
    }
}

C ++ 11より前は、自分で実装std::is_sorted_untilする必要があります。

于 2012-10-16T11:02:26.293 に答える
1

この非常に限られたケースでは、独自のバブルソートを作成する方がおそらくstd::sortよりも高速です。

于 2012-10-16T11:11:11.720 に答える
0

あなたがそのレベルの知識を持っているなら、あなたはあなたのためにそれを強制しようとするのではなく、あなた自身でアイテムを交換してみませsortんか？

確かにそれはより良い方法です。

どこに行けばいいのかわからなくても、すぐに見つけて取り外して、正しい位置に挿入することができます。

于 2012-10-16T11:02:32.603 に答える
0

このメソッドを使用して要素を移動できると思いますが、insertその「正しい」位置を計算する方法について詳しく知りたいと思います。より適切なアルゴリズムがある可能性があります。

于 2012-10-16T11:03:49.307 に答える
0

リストで可能なトラバーサルについて考えると、それは明らかにエンドツーエンドにすぎません。それで：

  • 順序が間違っている要素がどこにあるかわからない場合は、最初に要素が見つかるまで要素を1つずつスキャンする必要があります。
  • 値を覚えて、リストから順序が正しくない要素を削除してから、
  • 2つの可能性があります：
    • その要素は、これまでに遭遇した他のどの要素よりも並べ替え順序が大きくなります。その場合、挿入する正しい場所が見つかるまで、残りの要素を調べ続ける必要があります。
    • 要素は、既に渡した要素のどこかに属します。この場合、次のようになります。
      • 正しい場所が見つかるまで、最初の要素から後方または前方に移動できます。
      • 以前のトラバーサルからいくつかのレコードを作成した場合は、代わりにそれを使用して挿入場所をより速く見つけることができます。たとえばvector、リストiteratorのを作成した場合は、でバイナリ検索を実行できますvector。すべてのN番目の要素のベクトル、ハッシュテーブルなどは、他のすべての可能性です。
于 2012-10-16T11:08:20.350 に答える
0

これは、使用しない場合ですstd::list。

selectionSort(list,3)選択ソートアルゴリズムを使用すると、範囲がわかっている場合は、アイテム0〜3（）を単純にソートします。最後まで全範囲ではありません。

サンプルコード：

#include <iostream>
using namespace std;



void selectionSort(int *array,int length)//selection sort function 
{
    int i,j,min,minat;
    for(i=0;i<(length-1);i++)
    {
        minat=i;
        min=array[i];
      for(j=i+1;j<(length);j++) //select the min of the rest of array
      {
          if(min>array[j])   //ascending order for descending reverse
          {
              minat=j;  //the position of the min element 
              min=array[j];
          }
      }
      int temp=array[i] ;
      array[i]=array[minat];  //swap 
      array[minat]=temp;

    }
}

void printElements(int *array,int length) //print array elements
{

    int i=0;
    for(i=0;i<length;i++)     cout<<array[i]<<"  ";
    cout<<" \n ";
}

int main(void)
{

    int list[]={1,3,2,4,5,6};   // array to sort 
    int number_of_elements=6;

    cout<<" \nBefore selectionSort\n";
    printElements(list,number_of_elements);      


    selectionSort(list,3); 

    cout<<" \nAfter selectionSort\n";
    printElements(list,number_of_elements);      


    cout<<" \nPress any key to continue\n";
    cin.ignore();
    cin.get();

   return 0;
}

出力：

Before selectionSort
1  3  2  4  5  6

After selectionSort
1  2  3  4  5  6

Press any key to continue
于 2012-10-16T12:15:22.863 に答える