Sắp xếp mảng không dùng sort() trong JavaScript

Mô tả bài toán

Viết hàm sắp xếp mảng số sử dụng reduce() thay vì sort(). Thuật toán chèn từng phần tử vào vị trí thích hợp trong mảng kết quả.

Ví dụ minh họa

const arr = [4, 56, 5, 3, 34, 37, 89, 57, 98];

const sortWithReduce = arr => {
  return arr.reduce((acc, val) => {
    let ind = 0;
    while (ind < acc.length && val > acc[ind]) {
      ind++;
    }
    acc.splice(ind, 0, val);
    return acc;
  }, []);
};

console.log(sortWithReduce(arr));

Kết quả

[ 3, 4, 5, 34, 37, 56, 57, 89, 98 ]

Giải thích

Mỗi lần lặp, tìm vị trí chèn phù hợp trong mảng đã sắp xếp (acc) bằng vòng lặp while, sau đó dùng splice() chèn. Đây là thuật toán Insertion Sort triển khai bằng reduce.

Lưu ý

Độ phức tạp O(n²), chỉ phù hợp mảng nhỏ hoặc mục đích học tập. Với dữ liệu lớn nên dùng sort() gốc.