Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian là O(n^2). Tại sao việc sử dụng Bubble Sort để xử lý danh sách sản phẩm trên giao diện web lại là mộtanti-pattern nguy hiểm đối với Main Thread?

Question

Accepted Answer

1. Bản chất của Bubble Sort và độ phức tạp
Bubble Sort hoạt động bằng cách liên tục đổi chỗ các phần tử liền kề nếu chúng sai thứ tự. Với độ phức tạp thời gian trường hợp xấu nhất và trung bình là O(n^2), số lượng phép so sánh tăng theo cấp số nhân khi kích thước dữ liệu tăng.
2. Tác động đến Main Thread trong JavaScript
JavaScript sử dụng mô hình đơn luồng (Single-threaded Event Loop). Main Thread chịu trách nhiệm thực thi JavaScript, tính toán DOM, và render giao diện (Layout, Paint).
Khi bạn dùng Bubble Sort trên tập dữ liệu lớn (ví dụ hàng nghìn sản phẩm từ API):

Vòng lặp lồng nhau chạy hàng triệu phép tính chiếm toàn bộ tài nguyên của Main Thread.
Main Thread bị khóa (Blocking), không thể xử lý các sự kiện click của người dùng hoặc cập nhật khung hình từ trình duyệt (Frames).
Giao diện bị đóng băng (UI Freeze), gây hiện tượng giật lag, mất phản hồi nghiêm trọng.

3. Phương án giải quyết tối ưu ở cấp độ Junior

Tận dụng các thuật toán sắp xếp có sẵn được tối ưu hóa ở tầng native (như Array.prototype.sort() sử dụng Timsort với độ phức tạp trung bình O(n log n)).
Nếu bắt buộc phải xử lý dữ liệu cực lớn phía client, nên thực hiện phân trang (Pagination) hoặc tải vô hạn (Infinite Scrolling) để giới hạn số lượng phần tử cần sắp xếp trên RAM.
Chuyển việc sắp xếp về phía Server (Database Sorting) bằng các câu lệnh SQL (ORDER BY) để tận dụng tối ưu hóa Index của hệ quản trị cơ sở dữ liệu.

Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian là O(n^2). Tại sao việc sử dụng Bubble Sort để xử lý danh sách sản phẩm trên giao diện web lại là mộtanti-pattern nguy hiểm đối với Main Thread?

1. Bản chất của Bubble Sort và độ phức tạp

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi sorting liên quan cùng chủ đề