Khi thiết kế tính năng sắp xếp cho một danh sách hàng triệu bản ghi, tại sao việc sử dụng thuật toán QuickSort có thể dẫn đến rủi ro tràn bộ nhớ (Stack Overflow) và cách khắc phục?

Question

Accepted Answer

QuickSort dựa trên cơ chế đệ quy. Nếu chọn phần tử chốt (pivot) không tốt (ví dụ mảng đã sắp xếp sẵn), độ sâu của đệ quy có thể đạt đến O(n), dẫn đến tràn ngăn xếp (Stack Overflow). Để khắc phục, Junior cần: 1. Sử dụng chiến lược chọn pivot ngẫu nhiên hoặc chọn trung vị (median-of-three). 2. Chuyển đổi đệ quy thành vòng lặp với ngăn xếp thủ công. 3. Sử dụng các thuật toán thay thế như Heap Sort (độ phức tạp O(n log n) ổn định và không cần đệ quy sâu) hoặc tận dụng các thư viện đã được tối ưu hóa của ngôn ngữ lập trình.

Khi thiết kế tính năng sắp xếp cho một danh sách hàng triệu bản ghi, tại sao việc sử dụng thuật toán QuickSort có thể dẫn đến rủi ro tràn bộ nhớ (Stack Overflow) và cách khắc phục?

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ủ đề