私は「コーディングインタビューのクラッキング」(5e、119ページ)の本で分配関数を見てきました。以下にコピーしました:
int partition(int arr[], int left, int right){
int pivot = arr[(left + right) /2 ]; // Pick pivot point
while (left <= right) {
// Find element on left that should be on right
while (arr[left] < pivot) left++;
// Find the element on right that should be on left
while (arr[right] > pivot) right--;
// Swap elements, and move left and right indicies
if (left <= right) {
swap(arr, left, right); // swaps elements
left++;
right--;
}
}
return left;
}
この配列が与えられた場合:
1 2 3 4 5 6 3
これは、パーティションが段階的に私のために働いた方法です
- 4はピボット値です。左=0、右= 6
左=3、右=6。交換します。
1 2 3 3 5 6 4
左=4、右=4。終了
しかし、私が最終的に得た配列は次のとおりです。
1 2 3 3 5 6 4
4前後に分割されていません。手順を間違って実行しましたか、それともアルゴリズムが正しくありませんか?アルゴリズムの再現を再確認し、正しくコピーしました。
また、パーティションが左に戻っている理由はわかりませんが、ピボットを返しているのでしょうか。
ウィキペディアのパーティションとクイックソートの実装は理解していますが、ここで何が起こっているのか頭を悩ませようとしています。