1

私はクイックソートを理解しようとしていますが、一般的なアイデアは得ていますが、以下の質問に問題があります. 各反復後に配列に基づいて使用されているピボットを特定する簡単な方法はありますか?

Consider the following array and its state after iterations of QuickSort on the array: 

Initial Array: 32, 12, 17, 73, 40, 88, 16, 75 
After Iter 1: 32, 12, 17, 40, 16, 73, 88, 75 
After Iter 2: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 3: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 4: 12, 16, 17, 32, 40, 73, 88, 75 
After Iter 5: 12, 16, 17, 32, 40, 73, 75, 88

この QuickSort の実行で使用されるピボット選択戦略に名前を付けます。

ヒント: 各段階でピボットとして選択されている値を調べます。QuickSort は、最初に左のサブ配列とその左のサブ配列を再帰的に並べ替えてから、右のサブ配列を並べ替えることに注意してください。

4

1 に答える 1

1

任意の要素がピボットとして選択され、最初の反復で、ピボットよりも小さいすべての要素がピボットの左側に配置され、ピボットの右側に配置されていない場合は、それより大きい要素が配置されます。これは、必要に応じて、配列内でピボットを先にスワップすることを意味します。これを知って反復を見ると、ピボットを特定するのに役立ちます。

たとえば、上記の場合、中央の要素がピボット、つまり73として選択されていると思います。最初の反復の後、それよりも小さいすべての要素は左に移動し、それよりも大きい要素は右に移動します。

于 2012-10-31T07:09:39.483 に答える