Download miễn phí Đề tài Phương pháp Chèn trực tiếp - Insertion Sort
Khi tìm vị trí thích hợp để chèn a
vào đoạn a[0] đến a[i-1], do đoạn đã được sắp có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos giải thuật sắp xếp chèn nhị phân Binary Insertion Sort
Lưu ý: Chèn nhị phân chỉ làm giảm số lần so sánh, không làm giảm số lần dời chỗ.
Ngoài ra, có thể cải tiến giải thuật chèn trực tiếp với phần tử cầm canh để giảm điều kiện kiểm tra khi xác định vị trí pos.
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-02-11-de_tai_phuong_phap_chen_truc_tiep_insertion_sort.pqUH9fqjIT.swf /tai-lieu/de-tai-ung-dung-tren-liketly-58317/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phíTóm tắt nội dung tài liệu:
NHÓM 3 pro CÁC THÀNH VIÊN: 1.Dương Anh Vũ(giải thuật,đánh giá) 2.Hồ Thanh Phong(giải thuật,đánh giá) 3.Nguyễn Thị Thanh Tuyền(mô tả) 4.Ung Sĩ Cao Trân(mô tả) 5.Lê Văn Tình(định nghĩa) 6.Nguyễn Thị Mỹ Thu(định nghĩa) 7.Dương Công Thắng(máy tính,ĐN) 8.Lê Thành Thương(định nghĩa) Phương pháp Chèn trực tiếp Insertion Sort Insertion Sort – Ý tưởng Nhận xét : Mọi dãy a[0] , a[1] ,..., a[n-1] luôn có i-1 phần tử đầu tiên a[0] , a[1] ,... ,a[i-2] đã có thứ tự (2 ≤ i). Ý tưởng chính: Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a[0] , a[1] ,... ,a[i-1] trở nên có thứ tự. Vị trí này chính là pos thỏa : a[pos-1] a[i ]a) and (i 1 Then begin Tri_Ins (t,n - 1); If t[n] t[i - 1]); t := aux; End; Insertion Sort – Nhận xét Khi tìm vị trí thích hợp để chèn a vào đoạn a[0] đến a[i-1], do đoạn đã được sắp có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos giải thuật sắp xếp chèn nhị phân Binary Insertion Sort Lưu ý: Chèn nhị phân chỉ làm giảm số lần so sánh, không làm giảm số lần dời chỗ. Ngoài ra, có thể cải tiến giải thuật chèn trực tiếp với phần tử cầm canh để giảm điều kiện kiểm tra khi xác định vị trí pos. Insertion Sort – Đánh giá giải thuật Các phép so sánh xảy ra trong mỗi vòng lặp tìm vị trí thích hợp pos. Mỗi lần xác định vị trí pos đang xét không thích hợp dời chỗ phần tử a[pos-1] đến vị trí pos. Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau: *********THE END********** ...
