Triển khai QuickSort bằng chia để trị - JavaScript

Viết hàm JavaScript sắp xếp mảng số bằng thuật toán QuickSort.

QuickSort

Thuật toán chia để trị: chọn pivot, đặt các phần tử nhỏ hơn pivot bên trái, lớn hơn bên phải (sắp xếp tăng dần).

Ví dụ

Mã thực hiện:

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54]; 
const quickSort = (arr, left = 0, right = arr.length - 1) => { 
  let len = arr.length, index; 
  if(len > 1) { 
    index = partition(arr, left, right) 
    if(left < index - 1) { 
      quickSort(arr, left, index - 1) 
    } 
    if(index < right) { 
      quickSort(arr, index, right) 
    } 
  } 
  return arr 
} 
const partition = (arr, left, right) => { 
  let middle = Math.floor((right + left) / 2), 
  pivot = arr[middle], 
  i = left, 
  j = right 
  while(i <= j) { 
    while(arr[i] < pivot) { i++ } 
    while(arr[j] > pivot) { j-- } 
    if(i <= j) { 
      [arr[i], arr[j]] = [arr[j], arr[i]] 
      i++; j-- 
    } 
  } 
  return i 
} 
console.log(quickSort(arr));

Kết quả

Kết quả in ra console:

[ 
  2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434 
]