tailieunhanh - Giáo trình hướng dẫn sử dụng thuật toán hiệu chỉnh trong phân phối các cặp đường chạy lập trình p4

Ví dụ minh họa thuật toán sắp xếp trộn thẳng: Giả sử dữ liệu ban đầu trên tập tin Fd như sau: 10 Lần 1: L = 1 Phân phối luân phiên các đường chạy chiều dài L = 1 trên Fd về Ft1 và Ft2: Fd: Ft1: Ft2: 10 10 4 4 15 2 15 1 20 2 22 15 1 14 30 20 5 8 22 40 31 15 36 14 30 5 8 40 31 36 4 15 2 1 20 22 15 14 30 5 8 40 31 36 Ta tiến hành phân phối và trộn các đường chạy có chiều dài cố định L: | remove Templ remove Temp2 return -1 . if FileMerge Temp1 Temp2 DataFile L -1 remove Temp1 remove Temp2 return -1 L 2 L remove Temp1 remove Temp2 return 1 - Ví du minh họa thuật toán sap xếp trộn thẳng Gia sử dữ liệu ban đầu tren tập tin Fd như sau 10 4 15 2 1 20 22 15 14 30 5 8 40 31 36 Ta tiến hanh phân phối va trộn cac đường chay co chiều dài cố định L Lan 1 L 1 Phan phoi luan phiên cac đường chay chieu dai L 1 trên Fd ve Ft1 va Ft2 d 10 4 15 2 1 20 22 15 14 30 5 8 40 31 36 t1 10 15 1 22 14 5 40 36 t2 4 2 20 15 30 8 31 Trôn cac cạp đường chay tương ứng chieu dai L chay chieu dai L 2 thực te L co the nho hờn 2 1 tren Ft1 va Ft2 thanh cac đường 1 va đưa ve Fd t1 10 15 1 22 14 5 40 36 t2 4 2 20 15 30 8 31 d 4_ 10 2_ 15 1 20 15 22 14 30 5 8 31 40 36 Lan 2 L 2 Phan phoi luan phien cac đường chay chieu dai L 2 tren Fd ve Ft1 va Ft2 d 4 10 2 15 1 20 15 22 14 30 5 8 31 40 36 t1 4 10 1 20 14 30 31 40 t2 2_ 15 15 22 5 8 36 Trọn cac cặp đường chay tương ữ ng chieu dai L 2 tren Ft1 va Ft2 thanh cac đường chay chieu dai L 4 va đưa ve Fd t1 t2 4 2 10 15 1 15 20 22 14 5 30 8 31 36 40 d 2 4 10 15 1 15 20 22 5 8 14 30 31 36 40 Trang 68 Un 3 L 4 Phân phối luân phiên các đường chạy chiều dài L 4 trên Fd về Ft1 và Ft2 d 2 4 10 15 1 15 20 22 5 8 14 30 31 36 40 t1 2 4 10 15 5 8 14 30 t2 1 15 20 22 31 36 40 Trốn càc càp đường chày tường ưng chiêu dài L 4 trên Ft1 và Ft2 thành càc đường chày chiêu dài L 8 và đưà vê Fd t1 2 4 10 15 5 8 14 30 t2 1 15 20 22 31 36 40 d 1 2 4 10 15 15 20 22 5 8 14 30 31 36 40 Lan 4 L 8 Phàn phối luân phiên các đường chạy chiêu dài L 8 trên Fd vê Ft1 và Ft2 d 1 2 4 10 15 15 20 22 5 8 14 30 31 36 40 t1 1 2 4 10 15 15 20 22 t2 5 8 14 30 31 36 40 Trốn càc càp đường chày tương ưng chiêu dài L 8 trên Ft1 và Ft2 thành càc đường chày chiêu dài L 16 và đưà vê Fd. Thuàt toàn kêt thuc t1 1 2 4 10 15 15 20 22 t2 5 8 14 30 31 36 40 t1 1 2 4 5 8 10 14 15 15 20 22 30 31 36 40 - Phân tích thuật toán Trong thuàt giải này chúng ta luốn thực hiên log2 N làn phàn phối và trốn