Hỏi về 2 dòng trong thuật toán sort

[dung3 (Anh Dũng)]

chỗ này ạ

_# move pivots to center_
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

_# choose pivot_
swap a[n,rand(1,n)]

_# 3-way partition_
i = 1, k = 1, p = n
while i < p,
  if a[i] < a[n], swap a[i++,k++]
  else if a[i] == a[n], swap a[i,--p]
  else i++
end
_→ invariant: a[p..n] all equal_
_→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]_

_# move pivots to center_
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

_# recursive sorts_
sort a[1..k-1]
sort a[n-p+k+1,n]

[rogp10]

Theo mình thì nên chạy tay 10 lần phần phân đoạn trước đã

[dung3 (Anh Dũng)]

swap a[k…k+m-1,n-m+1…n]

chỗ này là thế nào ạ

[rogp10]

Do pivot đưa hết ra sau nên phải swap đoạn pivot với phần đầu đoạn “lớn hơn”. Cái này là swap từng cặp theo đúng thứ tự đó.