Алгоритм Hoare Quicksort не работает должным образом

Question

То есть с массивом

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

с использованием алгоритма разбиения Хоара я ожидаю

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

Но алгоритм из моего кода дает мне

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

i 'Я дословно следую этому алгоритму

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 {
    // ...

Кроме того, psuedocode сообщает

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)]

else 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 не приводит к пробелам между элементами массива)