Sắp xếp mảng bằng thuật toán Quick Sort trong JavaScript

Sắp xếp mảng bằng thuật toán Quick Sort trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số và sử dụng thuật toán Quick Sort để sắp xếp nó.

QuickSort:

Đây là thuật toán chia để trị, trong đó chúng ta chọn một phần tử chốt (pivot) trong mỗi vòng lặp và đặt tất cả các phần tử nhỏ hơn pivot về bên trái, các phần tử lớn hơn về bên phải (nếu sắp xếp tăng dần, ngược lại nếu giảm dần).

Ví dụ

Mã thực hiện như sau:

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// Tìm phần tử "pivot" trong mảng để so sánh với tất cả các phần tử khác
// sau đó dịch chuyển các phần tử trước hoặc sau pivot tùy thuộc vào giá trị của chúng
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, // Con trỏ bắt đầu tại phần tử đầu tiên
  j = right // Con trỏ bắt đầu tại phần tử cuối cùng
  while(i <= j) {
    // Di chuyển con trỏ trái sang phải cho đến khi giá trị tại trái lớn hơn giá trị pivot
    while(arr[i] < pivot) {
      i++
    }
    // Di chuyển con trỏ phải sang trái cho đến khi giá trị tại phải nhỏ hơn giá trị pivot
    while(arr[j] > pivot) {
      j--
    }
    // Nếu con trỏ trái nhỏ hơn hoặc bằng con trỏ phải, thì hoán đổi giá trị
    if(i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]] // Hoán đổi destructuring ES6
      i++
      j--
    }
  }
  return i
}
console.log(quickSort(arr));

Đầu ra

Kết quả trong console:

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