Example of partitioning 21387564
Example of partitioning 1 p 3 8 7 5 6 4 i j 2 r
Example of partitioning 21387564
Example of partitioning 1 p 3 8 7 5 6 4 i j 2 r
Example of partitioning 21387564 7. exchange
Example of partitioning 1 p 3 8 7 5 6 4 i j 2 r 7. exchange A [ r] ↔ A [ i + 1]
Example of partitioning 2134756 8
Example of partitioning 1 p 3 4 7 5 6 8 i j 2 r
Partitioning subroutine PARTITION(A,p,)∥Ap…r 1. xAr /pivot= Alpl 2.i←p-1 3.forj←ptor-1 4. do ifAljsx 5. then i←i+1 exchange A[+Al 7. exchange Ar]++Ai+1 8. return i+ 1
Partitioning subroutine PARTITION (A, p, r ) //A [p … r ] 1. x ← A [ r ] //pivot = A [p ] 2. i ← p − 1 3. for j ← p to r − 1 4. do if A [j] ≤ x 5. then i ← i + 1 6. exchange A [ i] ↔ A [j ] 7. exchange A [ r] ↔ A [ i + 1] 8. return i + 1 ≤ x x ≤ x p ? i j r