Thư Viện Câu Hỏi Phỏng Vấn

Question

Trong JavaScript, tại sao việc sử dụng hàm so sánh (compare function) trong phương thức Array.prototype.sort() lại là bắt buộc khi làm việc với mảng đối tượng (Array of Objects) thay vì chỉ gọi sort() không tham số?

Junior

Answer 1

Khi gọi sort() không tham số, JavaScript sẽ chuyển đổi các phần tử thành chuỗi (string) và so sánh theo thứ tự mã Unicode (UTF-16). Đối với mảng đối tượng, kết quả sẽ là '[object Object]', dẫn đến việc không thể sắp xếp đúng ý đồ. Để sắp xếp mảng đối tượng, bạn phải cung cấp một hàm so sánh (compare function) nhận vào hai tham số a và b. Ví dụ: data.sort((a, b) => a.price - b.price);. Hàm này trả về giá trị âm nếu a < b, dương nếu a > b, và 0 nếu bằng nhau. Đây là tiêu chuẩn để đảm bảo tính chính xác trong logic nghiệp vụ.

Answer 2

Insertion Sort có độ phức tạp O(n^2) trong trường hợp xấu nhất, nhưng nó cực kỳ hiệu quả đối với các tập dữ liệu nhỏ (thường dưới 10-20 phần tử) hoặc dữ liệu đã gần như được sắp xếp sẵn. Do chi phí khởi tạo thấp và tính ổn định (stable), các thuật toán hiện đại như Timsort (sử dụng trong V8 engine của Chrome) kết hợp Merge Sort với Insertion Sort để tối ưu hóa hiệu năng trên các phân đoạn nhỏ, giúp giảm thiểu chi phí đệ quy và tối ưu hóa bộ nhớ đệm (cache locality).

Answer 3

Việc sắp xếp tại Database tận dụng tối đa các chỉ mục (Index) đã được tối ưu hóa sẵn. Khi dữ liệu lớn, việc truyền tải toàn bộ tập dữ liệu về ứng dụng (Application-level) gây lãng phí băng thông mạng và tiêu tốn bộ nhớ RAM của Server. Ngoài ra, Database có khả năng thực hiện sắp xếp ngoài (External Sorting) nếu dữ liệu vượt quá RAM. Việc dùng ORDER BY kết hợp với LIMIT và OFFSET còn giúp triển khai tính năng phân trang (pagination) hiệu quả, giảm tải cho hệ thống.

Answer 4

Một thuật toán sắp xếp ổn định (Stable Sort) là thuật toán giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau. Nếu thuật toán không ổn định, khi bạn sắp xếp theo tên sản phẩm sau khi đã sắp xếp theo giá, các sản phẩm có cùng giá sẽ bị xáo trộn thứ tự tên ban đầu. Điều này gây trải nghiệm người dùng kém và khó kiểm soát dữ liệu. Trong thực tế, các thư viện chuẩn như Array.prototype.sort() trong các phiên bản ECMAScript mới đã được quy định là ổn định để đảm bảo tính nhất quán này.

Answer 5

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.

Answer 6

1. Nguyên nhân cốt lõi

Mặc định, phương thức Array.prototype.sort() trong JavaScript sẽ chuyển đổi các phần tử thành chuỗi (string) và thực hiện so sánh theo thứ tự từ điển (lexicographical order) dựa trên mã Unicode của từng ký tự, thay vì so sánh giá trị số học.