🫤 Quick Sort là gì ?

Lưu ý: Trong thuật toán sắp xếp nhanh, trục là phần tử được chọn từ mảng được dùng làm điểm tham chiếu để phân vùng mảng thành hai mảng con nhỏ hơn.

🌟 Triển khai thuật toán sắp xếp nhanh với Javascript

1. Chọn một phần tử trục từ mảng.

2. Phân vùng mảng thành hai mảng con, một mảng chứa các phần tử nhỏ hơn trục và mảng còn lại chứa các phần tử lớn hơn trục.

3. Áp dụng đệ quy thuật toán sắp xếp nhanh cho hai mảng con cho đến khi toàn bộ mảng được sắp xếp.

javascript
const quickSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }

  let pivot = arr[0];
  let leftArr = [];
  let rightArr = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      leftArr.push(arr[i]);
    } else {
      rightArr.push(arr[i]);
    }
  }

  return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
};

Bước 1: Chọn một phần tử Pivot

javascript
const pivot = arr[0];

Bước 2: Phân tách Mảng

javascript
let leftArr = [];
let rightArr = [];

for (let i = 1; i < arr.length; i++) {
  if (arr[i] < pivot) {
    leftArr.push(arr[i]);
  } else {
    rightArr.push(arr[i]);
  }
}

Bước 3: Sắp xếp đệ quy cho Mảng con

javascript
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];

Bước 4: Xác định trường hợp cơ sở

javascript
if (arr.length <= 1) {
  return arr;
}

👌 Kiểm tra thuật toán

javascript
let myArray = [3, 7, 2, 5, 1, 4, 6, 8];
console.log(quicksort(myArray)); // Output: [1,2,3,4,5,6,7,8]

✨ Kết thúc