Tại sao Insertion Sort có độ phức tạp O(n2) lớn hơn của Merge Sort và Quick Sort vẫn được sử dụng trong thực tế?
Mời các bạn lựa chọn những đáp án đúng dưới đây:
A. Insertion Sort có tốc độ nhanh hơn trong 1 số bài toán sắp xếp cụ thể.
B. Insertion Sort được sử dụng thay mergesort, quicksort khi kich thước mảng đủ nhỏ.
C. Insertion Sort được sử dụng khi cần stable sort.
D. Insertion Sort được sử dụng khi cần inplace sort.
Đáp án: A, B là hai lựa chọn đúng. Bạn Sơn Vũ và Tâm có chia sẻ các ý tương tự với ý kiến của team ra đề.
Giải thích:
A- Giống như bạn Sơn Vũ và Tâm có chia sẻ, Insertion Sort hoạt động hiệu quả trên một vài bài toán như: Có một mảng đã sắp xếp sẵn, cần liên tục chèn thêm phần tử mới vào mà vẫn phải đảm bảo danh sách vẫn được duy trì trạng thái sắp xếp.
B - Đối với trường hợp mảng nhỏ, ví dụ như mảng có khoảng 10 phần tử, thì 2 thuật toán Quick sort và Merge sort phải tốn chi phí bộ nhớ do đệ quy hoặc mảng phụ, nên sẽ chạy không hiệu quả bằng thuật toán Insertion sort.
C và D - Merge sort hoặc Quick sort đểu có thể đáp ứng được stable sort và inplace nên đáp án C và D là không chính xác.
Quiz được đăng trên Newsletter #11, đọc online số newsletter này ở đây: http://newsletter.grokking.org/issues/11-xay-d-ng-tinh-nang-autocomplete-tren-quora-90473