Challenge: Insertion Sort vs Merge/Quick Sort

grokking 2018-01-10 07:22:34 UTC #1

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 các bạn lựa chọn những đáp án đú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

motsach_theky 2018-01-12 03:38:13 UTC #2

Theo mình nhớ là Merge Sort chạy cần bộ nhớ lớn, cụ thể là additional space vào khoảng O(n).
Trong khi Insert Sort thực chất là các thao tác swap nên ko tốn nhiều bộ nhớ :-? additional space là O(1) thôi.
Nên Insert sort có thể tiết kiệm chi phí về bộ nhớ hơn Merge Sort.

Mà stable sort và inplace sort nghĩa là gì nhỉ? Ai giải thích giùm mình với! Xin cảm ơn

vtloc 2018-01-12 04:49:30 UTC #3

Theo mình hiểu thì không biết đúng không thì stable sort tức là thứ tự của các records có cùng key được đảm bảo sau khi sort. Ví dụ như có mảng các records:
* (2, a)
* (12, x)
* (11, xa)
* (5, k)
* (8, xb)
* (8, bx)
* (8, am)
* (6, dm)

Nếu yêu cầu là sắp xếp lại mảng trên dựa vào giá trị của field đầu tiên theo kiểu stable sort, tức là sau khi sắp xếp xong thì các phần tử phải có thứ tự như sau:
* (2, a)
* (5, k)
* (6, dm)
* (8, xb)
* (8, bx)
* (8, am)
* (11, xa)
* (12, x)

trong đó các records có key 8 có thứ tự vẫn giữ nguyên so với danh sách ban đầu.

Minh_Tam_Phan 2018-01-12 09:27:09 UTC #4

Theo minh là câu B. Vì:

Đối với các mảng nhỏ thì Insertion Sort sắp xếp hiệu quả hơn do không cần mảng phụ như Merge Sort, Còn Quick Sort yếu điểm là tính đệ qui, và hiệu quả của Quick Sort phụ thuộc vào cách chọn phần tử cầm canh.Insertion Sort là thuật toán xắp xếp nhanh nhất trên các mảng hầu như đã xắp (nghĩa là thời gian chạy phụ thuộc rất mạnh vào thứ tự hiện có của mảng). vì ưu điểm này để cải tiến Quick Sortng ta thường không gọi đệ qui trên các mảng nhỏ thay vào đó ng ta gọi lệnh Insertion Sort cho những mảng có kích thước M. M trong khoảng 5 -> 25 có thể cải thiện đến 20% chạy của Quick Sort. còn Merge Sort cũng dựa trên tư tưởng không thực hiện Merge Sort trên các mảng đó mà cũng gọi Insertion Sort cho các mảng nhỏ sau đó Merge nó lại tuật toán này được gọi làm Tim Sort, Python sử dung thuật toàn này cho 2 hàm sorted() sort().
Tham khảo https://www.geeksforgeeks.org/quick-sort/

svu 2018-01-12 09:35:32 UTC #5

Insertion nhanh hơn trong trường hợp dãy đã được sắp xếp gần đúng (chỉ có vài phần tử out-of-place), khi này độ phức tạp sẽ là O(n). Ngoài ra, mặc dù O(n^2) của insertion sort cao hơn O(nlogn) của mergesort và quicksort, nhưng với ít phần tử thì insertion sort vẫn nhanh hơn. Ngoài ra insertion sort cũng vừa stable và in place. Merge sort thì stable nhưng ko in place, và quick sort có 2 phiên bản: in place nhưng không stable và stable nhưng không in place.