0

私はこのメソッドが何をするのかを正確に理解しようとしています.「最も外側の間違った位置にあるペアを交換し続ける」と仮定しています. これをプログラムに入れて別の配列を試しましたが、結果は意味がありません。これは正確には何をしますか

partition(A, p)  
A: array of size n, p: integer s.t. 0 <= p < n

 1. swap(A[0],A[p])

 2. i <- 1, j <- n − 1

 3. while i < j do

 4.   while A[i] <= A[0] and i < n do

 5.     i <- i + 1

 6.   while A[j] > A[0] and j > 0 do

 7.     j <- j − 1

 8.   if i < j then

 9.     swap(A[i], A[j])

10. swap(A[0], A[j])

11. return j
4

1 に答える 1

1

この擬似コードが実装するアルゴリズムは、クイックソート ソート アルゴリズムのパーティショニング フェーズです。より小さいか等しいすべての値A[p]が左側にあり、すべてのより大きい値が右側にあるように、配列を配置します。が等しいj左側の最後のインデックスであるインデックスを返します。A[j]A[p]

クイックソートに慣れていない場合は、このパーティション アルゴリズムを使用して配列を「小さい」部分と「大きい」部分に分割し、各部分を再帰的にソートすることを目的としています。小さいものは配列内で大きいものより前に来るように配置されているため、配列はソートされます。pが適切に選択さA[p]れ、 が の値の中央近くにある場合A、これは非常に高速な並べ替え方法です。

于 2010-02-06T23:52:24.173 に答える