tailieunhanh - Phương pháp chèn trực tiếp
Tham khảo tài liệu 'phương pháp chèn trực tiếp', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | NHÓM 3 pro CÁC THÀNH VIÊN: Anh Vũ(giải thuật,đánh giá) Thanh Phong(giải thuật,đánh giá) Thị Thanh Tuyền(mô tả) Sĩ Cao Trân(mô tả) Văn Tình(định nghĩa) Thị Mỹ Thu(định nghĩa) Công Thắng(máy tính,ĐN) 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[pos] (1 pos i). Chi tiết hơn: Dãy ban đầu a[0] , a[1] ,., a[n-1], xem như đã có đoạn gồm một phần tử a[0] đã được sắp. Thêm a[1] vào đoạn a[0] sẽ có đoạn a[0] a[1] được sắp Thêm a[2] vào đoạn a[0] a[1] để có đoạn a[0] a[1] a[2] được sắp Tiếp tục cho đến khi thêm xong a[n-1] vào đoạn a[0] a[1] .a[n-1] sẽ có dãy a[0] a[1] A[n-1] được sắp. Insertion Sort – Ý tưởng Insertion Sort – Thuật toán //input: dãy (a, n) //output: dãy (a, n) đã được sắp xếp Bước 1: i = 2; // giả sử có đoạn a[0] đã được sắp Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i] để chèn x vào Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho x Bước 4: a[pos] = x; // có đoạn a[0]a[i] đã được sắp Bước 5: i = i+1; Nếu i n : Lặp lại Bước 2. Ngược lại : Dừng. Insertion Sort – Ví dụ 2 8 5 1 6 4 15 12 2 3 4 5 6 7 8 1 2 8 5 1 6 4 15 12 i x 2 3 4 5 6 7 8 1 pos 2 Insertion Sort – Ví dụ Chèn a[1] vào (a[0], a[1]) 12 8 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Chèn a[2] vào (a[0] a[2]) 8 8 12 5 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Chèn a[3] vào (a[0] a[3]) 5 5 8 12 1 6 4 15 2 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Chèn a[4] vào (a[0] a[4]) 1 2 5 8 12 6 4 15 1 i x 2 3 4 5 6 7 8 1 pos Insertion Sort – Ví dụ Chèn a[5] vào (a[0] a[5]) 6 2 5 6 8 12 4 15 1 | NHÓM 3 pro CÁC THÀNH VIÊN: Anh Vũ(giải thuật,đánh giá) Thanh Phong(giải thuật,đánh giá) Thị Thanh Tuyền(mô tả) Sĩ Cao Trân(mô tả) Văn Tình(định nghĩa) Thị Mỹ Thu(định nghĩa) Công Thắng(máy tính,ĐN) 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[pos] (1 pos i). Chi tiết hơn: Dãy ban đầu a[0] , a[1] ,., a[n-1], xem như đã có đoạn gồm một phần tử a[0] đã được sắp. Thêm a[1] vào đoạn a[0] sẽ có đoạn a[0] a[1] được sắp Thêm a[2] vào đoạn a[0] a[1] để có đoạn a[0] a[1] a[2] được sắp Tiếp tục cho đến khi thêm xong a[n-1] vào đoạn a[0] a[1] .a[n-1] sẽ có dãy a[0] a[1] A[n-1] .
đang nạp các trang xem trước
