2

今週の火曜日に予定されているテストのために、さまざまな並べ替えおよび検索アルゴリズムを研究しようとしています。クイックソートアルゴリズムにたどり着くまで、すべてうまくいきました。私は本も他のリソースも持っていなかったので、オンラインでSparkNoteを読み始めました。テキストは理解できたと思い、オンラインで見つけたPowerPointの Quick Sort Algorithm の部分も読みました。

ただし、SparkNote は、アルゴリズムの段階的なプロセスのページで例を提供しましたが、最初にリストを配置する手順は示していませんでした。与えられたリストは[5 9 3 8 6 4 2 1 7 0]. SparkNotes によると、左側のピボット (5) より小さい値と右側のピボットより大きい値を持つ配置されたリストは です [0 3 4 2 1 5 8 6 7 9]。ただし、自分で手順を実行しようとすると、[ 4 0 3 1 2 5 6 8 7 9 ].

私が取った手順は次のとおりです。

5 9 3 8 6 4 2 1 7 0 // The initial list. Pivot = 5
5 0 3 8 6 4 2 1 7 9 // Switched 0 and 9.
5 0 3 1 6 4 2 1 7 9 // Switched 8 and 1
5 0 3 1 2 4 6 8 7 9 // Switched 6 and 2
4 0 3 1 2 5 6 8 7 9 // Switched 4 and 5 because the lines that point to the 
                    // greater and smaller numbers crossed.

私の間違いはどこですか？また、5 未満の数字は左側にあり、5 より大きい数字は右側にあることがわかりますが、私の間違いは並べ替えに本当に影響しますか?

4

3 に答える 3

3

SparkNotesで説明されているアルゴリズムは、最初にピボット要素を配列の右端の位置に配置します。使用したアルゴリズムは、ピボットを左端の位置に配置/保持しました。分割後の配置が異なるのも不思議ではありません。

それは彼らが始めたことを意味します

5 9 3 8 6 4 2 1 7 0

ピボットとして選択5し、右端の位置に配置しました（交換5および0）

0 9 3 8 6 4 2 1 7 5

その後、残りの要素のパーティショニングを実行しました。

左端の位置を維持5しました（SparkNotesからステップ2を実行するのを忘れたようです）。結局、両方のバリアントが機能します。つまり、「間違い」はありません。あなたの場合、配列は正しく分割されており、配置は完全に有効です。

于 2012-08-11T20:22:39.867 に答える
1

ここでは、クイック ソートアルゴリズムの視覚的な実装を確認できます。

そして多分あなたも役に立つでしょう：

ハンガリーの民族舞踊が嫌いな方は、リンク先に行かないでください。:)

于 2012-08-11T20:37:51.367 に答える
0

sparknotes サイトに示されている正確なアルゴリズムに従っていませんでした。ステップ 2 では、ピボットを最後の要素と交換する必要があります。

いずれにせよ、ピボットの前のすべての要素がピボットよりも小さく (または等しく) なり、ピボットに続く要素が大きくなるように (または等しく) シーケンスを分割する限り、パーティション分割を正確に実行する方法はアルゴリズムには関係ありません (または同等）。結果のパーティションを再帰的にソートすると、最終的にソートされたシーケンスになります。

正確さではなく、効率の問題、等しい要素を処理する方法、ピボットを選択する方法、および最終的に別のアルゴリズムに切り替えるシーケンスの長さです。

于 2012-08-11T20:27:36.877 に答える