3

数字のリストを並べ替える並べ替え手法を作成しようとしています。しかし、それが行うことは、2 つの数値を比較することです。最初の数値はリストの最初の数値であり、もう 1 つの数値は 2 k - 1 のインデックスになります。

2^k - 1 = [1,3,7, 15, 31, 63...]

たとえば、リストがある場合[1, 4, 3, 6, 2, 10, 8, 19]

このリストの長さは 8 です。したがって、プログラムは 2 k - 1 リストで 8 未満の数値を見つける必要があります。この場合は 7 になります。

そのため、ランダム リストの最初の数字 (1) と同じリストの 7 番目の数字 (19) を比較します。2 番目の数値より大きい場合は、位置が入れ替わります。

このステップの後、4 とその後 7 番目の数に続きますが、それは存在しないため、3 は 2 k - 1 の次の数であるため、4 の後の 3 番目の数と比較する必要があります。

したがって、4 と 2 を比較し、適切な場所にない場合は交換する必要があります。したがって、リストが最終的にソートされる1 in 2 k - 1に到達するまで、これは継続する必要があります。

このコードを使い始めるのに助けが必要です。

これまでのところ、2 k - 1 のリストを作成する小さなコードを書きましたが、それは私が得た限りです。

a = []

for i in range(10):
    a.append(2**(i+1) -1)

print(a)

例：

シーケンス V = 17,4,8,2,11,5,14,9,18,12,7,1 の並べ替えを検討してください。スキッピング シーケンス 1、3、7、15、… は、適合する最大値として r=7 を生成するため、V を見ると、最初のスパース サブシーケンス = 17,9 であり、V に沿って渡すと 9,4,8​​ が生成されます。最初のスワップ後は ,2,11,5,14,17,18,12,7,1、r 使用後は 9,4,8​​,2,1,5,14,17,18,12,7,11 =7 完全に。a=3 (スキッピング シーケンスの次の小さい項) を使用すると、最初のスパース サブシーケンス = 9,2,14,12 を V に適用すると、2,4,8,9,1,5,12,17 が得られます。 18,14,7,11、および残りのa = 3並べ替えは 2,1,8,9,4,5,12,7,18,14,17,11 を返し、次に 2,1,5,9,4,8​​ を返します,12,7,11,14,17,18. 最後に、 でa = 11,2,4,5,7,8,9,11,12,14,17,18 を取得します。

最後にスキップなしで並べ替えを行うことを考えると、最初の唯一のステップとして最後のステップを単純に実行するよりもなぜこれが速いのでしょうか。シーケンスを通過するコームと考えてください。前のステップでは、コースコームを使用して遠いものを正しい順序で取得し、最終的に微調整でほぼ処理するまで、徐々に細かいコームを使用していることに注意してください。 -ほとんど調整を必要としない並べ替えられたシーケンス。

p = 0
x = len(V) #finding out the length of V to find indexer in a
for j in a: #for every element in a (1,3,7....)
    if x >= j: #if the length is greater than or equal to current checking value
        p = j #sets j as p

それで、リストの最初の数値と比較する距離を見つけますが、距離が範囲外になるまでそれを続ける何かを書く必要があるので、3から1に切り替えてから、リストまで小さい距離をチェックしますソートされます。

4

1 に答える 1

4

実際に説明しているソートアルゴリズムはCombsortと呼ばれます。実際、より単純なバブルソートは、ギャップが常に 1 で変化しないコムソートの特殊なケースです。

これを開始する方法に行き詰まっているので、次のことをお勧めします。

  1. 最初にバブルソート アルゴリズムを実装します。ロジックはより単純であり、それを作成する際の推論がはるかに簡単になります。
  2. これが完了すると、重要なアルゴリズム構造が整い、そこからギャップ長の計算をミックスに追加するだけです。これは、特定の式でギャップの長さを計算することを意味します。次に、ループ制御インデックスと内部比較インデックスを変更して、計算されたギャップ長を使用します。
  3. ループを反復するたびに、ギャップの長さをスケーリング量だけ減らします (実際にはコームを短くします)。
  4. 最後のステップは、さまざまなギャップの長さと数式を試して、アルゴリズムの効率にどのように影響するかを確認することです。
于 2013-07-27T01:56:24.987 に答える