制限で整数をソートする

Question

整数の配列を持つ場合、ステップごとに許される操作が1つしかない場合、ソートするために必要な最小のステップをどのように決定できますか？ 例えば、我々は

7 8 9 11 1 10

を有するならば、第1ステップにおいて一方が1 7 8 9 10 11を取得する右端及び左端に第2段階の動き1 11を移動させることができます。したがって、合計ステップ= 2 ここでバブルソートを適用できますか？最悪の場合の複雑さはO（n^2）となります。それでは、もっと効率的にするにはどうしたらいいですか？おかげさまで

Answer 1

この問題を少し解明できますか？あなたがリストを言うとき、あなたはリンクされたリストを意味しますか、または配列を意味しますか？リンクされたリストでない場合は、限られた操作セットで少し混乱します。リンクされたリストであれば、おそらくO（nlgn）の平均時間で実行されるquicksortを変更できます。

Answer 2

あなたが言及しているデータ構造は、基本的にリンクリストです。リンクリストの場合は、quicksortまたはmergesort（O（nlogn））を使用できます。

Answer 3

ここでは、O（n log n）時間、O（n）補助空間、および正確にn回のMoveToFront操作を行うソリューションです。入力配列を指定

、Aは、二番目の配列、Bは、そうのような値/インデックス対と...

7 8 9 11 1 10 -> (7 0) (8 1) (9 2) (11 3) (1 4) (10 5) 
[this step takes O(n) time and O(n) space] 

は、各ペアの値の大きい順にBをソートしてください.. 。

(7 0) (8 1) (9 2) (11 3) (1 4) (10 5) -> (11 3) (10 5) (9 2) (8 1) (7 0) (1 4) 
[this step takes O(n log n) time] 

次の操作を行うBの各要素のための今すぐバイナリ検索ツリー、T.

を準備...

ここ

このアルゴリズムはあなたの例の配列

(11 3) 
    I := 3 
    V := 3 + 0 = 3 
    MoveToFront(3): 7 8 9 11 1 10 -> 11 7 8 9 1 10 
    T:() -> (3) 

(10 5) 
    I := 5 
    V := 5 + 0 = 5 
    MoveToFront(5): 11 7 8 9 1 10 -> 10 11 7 8 9 1 
    T: (3) -> (3 5) 

(9 2) 
    I := 2 
    V := 2 + 2 = 4 
    MoveToFront(4): 10 11 7 8 9 1 -> 9 10 11 7 8 1 
    T: (3 5) -> (2 3 5) 

(8 1) 
    I := 1 
    V := 1 + 3 = 4 
    MoveToFront(4): 9 10 11 7 8 1 -> 8 9 10 11 7 1 
    T: (2 3 5) -> (1 2 3 5) 

(7 0) 
    I := 0 
    V := 0 + 4 = 4 
    MoveToFront(4): 8 9 10 11 7 1 -> 7 8 9 10 11 1 
    T: (1 2 3 5) -> (0 1 2 3 5) 

(1 4) 
    I := 4 
    V := 4 + 1 = 5 
    MoveToFront(5): 7 8 9 10 11 1 -> 1 7 8 9 10 11 
    T: (0 1 2 3 5) -> (0 1 2 3 4 5) 

に取り組んでいる私は、あなたがn MoveToFront /戻る操作よりも少ないを使用して、これらの配列をソートする方法を見つけることができます想像しますが、私はあなたがそれらを見つけることができるとは思いませんO（n log n）時間未満で実行される。しかし、これらの操作が遅い場合は、計画に時間がかかるアルゴリズムを使用する価値があります。そのため、操作の数を減らすことができます。

Answer 4

ソーティング問題のように私には聞こえません。いくつの動きをする必要があるのか​​を見つけるだけですが、配列をソートする必要はありません。私はそれがO（n log n）よりも速くできると確信しています。

私はそのような解を提案します： はa [i]> a [i - 1]を数えるだけです。それがあなたの結果です。

引数： [i]> [i-1]の場合は、[i]または[i-1]のいずれかがその場所にないことを意味します。だから、次のことができます。

1）[I-1]配列

2）の先頭に[i]は、配列の末尾に移動移動します。

Upd。あなたは配列の例として、あなたが移動している[i]か[i-1]を定義する必要があります：7 8 9 11 1 10 2つの比較があり、 > 1と11> 10.したがって、これは間違いなく動的プログラミングのタスクです。しかし、それはまだ高速ですO（n log n）