tailieunhanh - Giáo trình phân tích thuật toán hiệu chỉnh trong phân phối các cặp đường chạy tự nhiên p2

Trộn các cặp đường chạy tự nhiên tương ứng trên Ft1 và Ft2 thành các đường chạy tự nhiên trong đó đường chạy tự nhiên đầu tiên có chiều dài L = 2 và đưa về Fd: Ft1: Ft2: Fd: 80 24 24 5 11 80 5 12 2 10 11 2 35 12 15 35 2 2 18 1 4 10 15 18 35 35 1 4 6 6 | if Head 1 Temp j1 M I1 J1 else Temp J2 M I1 J2-- I1 FirstPair 0 if I1 I2 return Head 0 - Head break if I1 I2 Temp J1 M I1 if I1 N-1 L N return return void NaruralMergeSort1 T M int N int L 1 if N 2 return while M L-1 M L L N L T Temp new T N if Temp NULL return while L N NaturalMergeDistribute M N Temp L if L N for int I 0 I N I M I Temp I break . NaturalMergeDistribute Temp N M L delete Temp return Trang 58 - Ví dụ minh họa thuật toán Giả sử ta cần sap xếp mảng M có 10 phần tử sau N 10 M 51 39 45 55 20 15 20 17 40 10 Ta thực hiến cảc lần trón cảc cặp run tự nhiến ở hai đầu dầy nảy vả kết hợp phản phói cảc run mởi trón vế hai đầu dầy kia nhự sau Lần 1 L 1 Trón cảc cặp run tự nhiến có chiếu dải L1 1 vả L2 2 trến M thảnh cảc run có chiếu dải L 3 vả kết hợp phản phối luân phiến cảc run nảy vế hải đầu dầy Tmp M 45 Tmp Đói vai tró cua M vả Tmp chó nhau Lần 2 L 3 Trón cầc cầp run tự nhiến có chiếu dải L1 3 vả L2 5 trến M thảnh cầc run có chiếu dải L 8 vả kết hợp phản phói luản phiến cảc run nảy vế hải đầu dầy Tmp Đói vai tró của M và Tmp chó nhau 17 20 39 40 45 51 55 15 M 0 0 Lần 3 L 8 Trón cảc cảp run tự nhiến có chiếu dải L1 8 vả L2 2 trến M thảnh cảc run có chiếu dải L 10 vả kết hợp phản phói luản phiến cảc run nảy vế hải đầu dầy Tmp M 10 17 20 39 40 45 51 55 20 15 Tmp 10 15 17 20 20 39 40 45 51 5 Đói vai tró cua M vả Tmp chó nhau M 10 15 17 20 20 39 40 45 51 55 Trang 59 ỹiá ÙU Cấu Ttú Dũ Liệu vù ỹiùi 7huật L 10 Kết thúc thuật toán - Phân tích thuật toán trộn tự nhiên Trong trường hợp tot nhát khi dáy co thứ tự táng thì chúng tá không phái quá bước phán phoi vá trộn náo hết So phếp gán Gmin 1 So phếp so sánh Smin 2 N-1 2 2N So phếp hoán vị Hmin 0 Trong trường hợp xáu nhát khi dáy co thứ tự giám ợ nửá đáu vá co thứ tự táng ợ nửá cuối vá ợ moi bước trọn phán phoi thì đo dái đường cháy mời cũng chỉ táng gấp đoi. Trong trượng hợp náy sế giong như thuát toán trọn tháng đá hiếu chỉnh So phếp gán Gmáx NxLog2 N 1 So phếp so sánh Smáx 2NxLog2 N 2 So phếp hoán vị Hmin 0 Trun .