quick_sort.js

main()

function main () {
  let arr = [5, 8, 4, 2, 6, 1, 3, 9]
  console.log('original: ')
  printArray(arr)
  quickSort(arr, 0, arr.length - 1)
}

function swap (a, idx1, idx2) {
  const t = a[idx1]
  a[idx1] = a[idx2]
  a[idx2] = t
}

function quickSort (a, left, right) {
  let pl = left
  let pr = right
  let x = a[Math.round((left + right) / 2)]
  console.log('pivot is ', x)

  while (pl <= pr) {
    while (a[pl] < x) {
      pl = pl + 1
    }

    while (x < a[pr]) {
      pr = pr - 1
    }

    if (pl <= pr) {
      swap(a, pl, pr)
      pr = pr - 1
    }
  }

  printArray(a)

  if (left < pr) {
    quickSort(a, left, pr)
  }

  if (pl < right) {
    quickSort(a, pl, right)
  }
}

function printArray (a) {
  a.join(' ')
  console.log(a)
}


// output

/*

original: 
[ 5, 8, 4, 2, 6, 1, 3, 9 ]
pivot is  6
[ 5, 3, 4, 2, 1, 6, 8, 9 ]
pivot is  4
[ 1, 3, 2, 4, 5, 6, 8, 9 ]
pivot is  3
[ 1, 2, 3, 4, 5, 6, 8, 9 ]
pivot is  2
[ 1, 2, 3, 4, 5, 6, 8, 9 ]
pivot is  5
[ 1, 2, 3, 4, 5, 6, 8, 9 ]
pivot is  8
[ 1, 2, 3, 4, 5, 6, 8, 9 ]
pivot is  9
[ 1, 2, 3, 4, 5, 6, 8, 9 ]

*/