Hoare Quicksort算法无法正常工作

Question

所以有数组

[6, 3, 8, 7, 2, 5, -9, 1, 4, 10]

使用我期望的Hoare分区算法

[-9, 1, 2, 3, 4, 5, 6, 7, 8, 10]

但是我代码中的算法给了我

[4, 3, 8, 7, 2, 5, -9, 1, 6, 10]

我基本上逐字遵循此算法

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[(lo + hi) / 2]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

但是我的代码似乎无法产生正确的答案

const arr = [6, 3, 8, 7, 2, 5, -9, 1, 4, 10]
const mid = (a, b) => (a + b) / 2

function partition(A, lo, hi) {
  const midpoint = mid(lo, hi)
  const pivot = A[midpoint]
  let i = lo - 1
  let j = hi + 1
  do {
    i += 1
  } while (A[i] < pivot)
  do {
    j -= 1
  } while (A[j] > pivot)
  if (i < j) {
    const A_i = A[i]
    A[i] = A[j]
    A[j] = A_i
  } else {
    return j
  }
}

function quicksort(A, lo, hi) {
  if (lo < hi) {
    const p = partition(A, lo, hi)

    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)
  }
  return A
}
quicksort(arr, 0, arr.length - 1)

console.log(arr)
console.log('[-9, 1, 2, 3, 4, 5, 6, 7, 8, 10]' === JSON.stringify(arr))

Answer 1

某些问题：您缺少loop forever逻辑，因此在while(true)块之前插入do {：

while (true) {
  do {
    i += 1
  } while (A[i] < pivot)
  do {
    // ...

而且，伪代码说

quicksort(A, lo, p)
quicksort(A, p + 1, hi)

但是你有

quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)

因此，请删除- 1。

伪码中缺少的另一个问题是

pivot := A[(lo + hi) / 2]

实际上应该是

pivot := A[floor((lo + hi) / 2)]

否则pivot可能不是整数，该代码将无效。

解决这些问题，代码起作用：

function quicksort(A, lo, hi) {
  if (lo < hi) {
    const p = partition(A, lo, hi)
    quicksort(A, lo, p) // <---------------
    quicksort(A, p + 1, hi)
  }
}

function partition(A, lo, hi) {
  const pivot = A[Math.floor((lo + hi) / 2)];  // <---------------
  let i = lo - 1
  let j = hi + 1
  while (true) { // <---------------
    do {
      i += 1
    } while (A[i] < pivot)
    do {
      j -= 1
    } while (A[j] > pivot)
    if (i >= j) {
      return j;
    }
    [A[i], A[j]] = [A[j], A[i]]; // <---- easier syntax
  }
}

const arr = [6, 3, 8, 7, 2, 5, -9, 1, 4, 10]
quicksort(arr, 0, arr.length - 1)
console.log(arr)
console.log('[-9,1,2,3,4,5,6,7,8,10]' === JSON.stringify(arr))  // <---------------

（请注意，JSON.stringify不会在数组项之间产生空格）