thucnq

Thuật toán sắp xếp chèn làm việc cũng giống như tên gọi - Nó thực hiện việc quét một tập dữ liệu, với mỗi phân tử, thủ tục kiểm tra và chèn phần tử đó vào vị trí thích hợp trong danh sách đích (chứa các phần tử đứng trước nó đã được sắp xếp) được tiến hành.
Phương pháp dễ dàng nhất để thực hiện thuật toán này là dùng hai vùng chứa dữ liệu khác nhau - tập dữ liệu nguồn và tập dữ liệu mà các phần tử đã sắp xếp được chèn vào. Tuy nhiên để tiết kiệm bộ nhớ, hầu hết các ứng dụng đều chỉ sử dụng một tập dữ liệu duy nhất. Thuật toán được tiến hành bằng cách dịch chuyển phân tử hiện tại đang xét tuần tự qua những phân tử ở vùng dữ liệu phía trước đã được sắp xếp, phép hoán vị nó với phần tử liền kề được thực hiện một cách lặp lại cho tới khi tiến tới được vị trí thích hợp.

Do với mỗi phân tử, insertion sort cần thực hiện so sánh với các phần tử trước nó nên tối đa số lần duyệt dữ liệu là !N. Vì vậy cũng giống như Bubble sort, Insertion sort được coi là có độ phức tạp O(n2). Mặc dù có cùng độ phức tạp, Insertion sort hiệu quả hơn gần như hai lần so với Bubble sort, tuy nhiên vẫn không hiệu quả với tập dữ liệu lớn.

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán Sắp xếp chèn (Insertion sort) http://www.laptrinhviet.com/showthread.php?t=19823 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều