Chương 6Sắp thứ 2 – Heap Sort, Bubble Sort.(Buổi 10).Giới này trình bày hai phương pháp sắp : Heap Sort và Bubble SortTrường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 6: Sắp thứ thứ tự đống (Heap Sort).Dãy a[i], , a[j], , a[k] là một đống (heap) nếu:.a[j] ≥ a[2(j+1)].và a[j] ≥ a[2(j+1)-1].a[j]a[2(j+1)-1]98 a[2(j+1)]5Hình . Định nghĩa một đống (heap).Trường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 6: Sắp thứ thứ tự đống (Heap Sort)a[0] 9a[1] 5a[3] 38 a[2]a[4] 46 a[5]7 a[6]Hình . Ví dụ một đống (heap)Trường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 6: Sắp thứ a[0], , a[k] là một đống thì a[0] có khóa a[i], , a[k] bất kỳ thì nửa cuối của dãy này đốngDãy a[i] , a[k] là một đống thì mọi dãy con này là một đốngDãy a[i], , a[k] có thứ tự (giảm dần) thì dãy này đốngDãy a[i], , a[k] là một đống thì dãy này chưa thứ tựTrường Đại học Bách Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải 6: Sắp thứ . | Chương 6 Sắp thứ tự Phần 2 – Heap Sort, Bubble Sort (Buổi 10) Giới thiệu Phần này trình bày hai phương pháp sắp thứ tự: Heap Sort và Bubble Sort Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 6: Sắp thứ tự 2 Sắp thứ tự đống (Heap Sort) Dãy a[i], , a[j], , a[k] là một đống (heap) nếu: a[j] ≥ a[2(j+1)] và a[j] ≥ a[2(j+1)-1] a[j] a[2(j+1)-1] 9 8 a[2(j+1)] 5 Hình . Định nghĩa một đống (heap) Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 6: Sắp thứ tự 3 Sắp thứ tự đống (Heap Sort) a[0] 9 a[1] 5 a[3] 3 8 a[2] a[4] 4 6 a[5] 7 a[6] Hình . Ví dụ một đống (heap) Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 6: Sắp thứ tự 4 Heap Sort Tính chất Dãy a[0], , a[k] là một đống thì a[0] có khóa lớn nhất. Dãy a[i], , a[k] bất kỳ thì nửa cuối của dãy này là một đống. Dãy a[i] , a[k] là một đống thì mọi dãy con của dãy này là một đống. Dãy a[i], , a[k] có thứ tự (giảm dần) thì dãy này là một đống. Dãy a[i], , a[k] là một đống thì dãy này chưa chắc có thứ tự. Trường Đại học Bách Khoa Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 6: Sắp thứ .
