Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 5-8

] và kết thúc phân đoạn.7. Sắp xếp nhanhChia để trị và đệ quy	Sau khi đã xác định được vị trí của chốt, dãy cho trước chia thành 02 đoạn, thỏa mãn tính chất phân đoạn. Với mỗi đoạn lại tiến hành phân đoạn đệ quy cho đến khi trong dãy con hiện thời chỉ còn lại không quá hai số hạng. Dãy thu được sẽ là dãy được sắp.7. Sắp xếp nhanh7. Sắp xếp nhanh7. Sắp xếp nhanh7. Sắp xếp nhanhCHƯƠNG VII: SẮP XẾP7. Sắp xếp nhanhCHƯƠNG VII: SẮP XẾP7. Sắp xếp nhanhĐánh giá và nhận xétCó hướng tổng quát tốtSử dụng ít tài nguyênPhép toán tích cực cũng là phép toán so sánh, thỏa mãn công thức truy hồi sau:CN = 2CN/2 +N Dễ dàng nhận được: CN = NlgNChỉ sử dụng trung bình NlgN thao tác để sắp xếp N phần tửVấn đề chọn chốt.Quyết định tính hiệu quảCần chọn điểm chốt tốt hơnChọn ngẫu nhiên 03 phần tử trong dãy, sau đó chọn phần tử giữa của 03 phần tử này làm phân hoạch. Chẳng hạn số hạng trái , phải, giữa. Phương pháp này đảm bảo, trường hợp xấu nhất không thể xẩy ra. 8. Sắp xếp bằng cơ sốÝ tưởngÁp dụng tư tưởng phân đoạn để sắp xếp dãy khóa là số tự nhiên theo thứ tự không giảm.Sắp xếp bằng cơ số theo kiểu hoán vị các khóa Ta có thể coi mỗi số nguyên là một dãy z bit đánh số từ 0 đến z-1.Để phân đoạn ta có thể đưa các khóa có bít cao nhất bằng 0 về đầu dãy, những khóa có bit cao nhất bàng 1 về cuối dãy (vì những khóa bắt đầu bằng 0 ở bít cao nhất sẽ nhỏ hơn những khóa có bít cao nhất bằng 1). Tiếp tục phân đoạn với hai đoạn dãy khóa, một đoạn có bít cao nhất bàng 1 và một đoạn có bít cao nhất bằng 0. Ví dụ, dãy xuất phát là 1,3,7,6,,5,2,3,4,4,5,6,7 tương ứng với dãy 03 bit:001 011 111 110 101 010 011 100 100 101 110 111Phân đoạn dựa vào bit cao nhất ( bên trái cùng) 001 011 011 010  101 110 111 100 100 101 110 111Pân đoạn dựa vào bít thứ 2 từ trái sang001 011 011 010 101 101 100 100 111 110 110 111.Tiếp tục phân đoạn dựa vào bit ở hàng đơn vị001 010 011 011 100 100 101 101 110 110 111 111Có thể thực hiện với hệ cơ số khác bất kìĐộ phức tạp thuật toán: Để phân đoạn bằng 1 bít thì cần Cn thời gian, nên thời gian phân đoạn bằng z bit se là C.N.z ( C là hằng số), vậy trường hợp xấu thì độ phức tạp thuật toán là O(N.z) còn trường hợp trung bình là O(N. min (z,lgN) 8. Sắp xếp bằng cơ sốSắp xếp bằng cơ sốSử dụng một thuật toán nào đó để sắp xếp dãy khóa tăng dần theo giá trị chữ số hàng đơn vị.Sử dụng một thuật toán sắp xếp ổn định nào đó để sắp xếp dãy khóa tăng dần theo giá trị chữ số hàng chục.Tiếp tục thực hiện tương tự với chữ số hàng trăm, ngàn,Nhận xét và đánh giáCó thể coi số chữ số của mỗi khóa là bằng nhau ( bổ sung các chữ số 0 vào bên trái mỗi số hạng còn thiếu).Độ phức tạp phụ thuộc chủ yếu vào độ phức tạp các thuật toán sắp xếp khác đã được lựa chọn. 9. Tính ổn định của thuật toán sắp xếpMột phương pháp sắp xếp được gọi là ổn định nếu nó bảo toàn thứ tự bản ghi có khóa bằng nhau trong danh sách.Trong số các thuật toán đã xét: Các thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chèn là những thuâth toán ổn định, các thuật toán còn lại là không ổn định. Nói chung mọi phương pháp sắp xếp không ổn định đều có thể biến đổi để nó trở thành ổn định. Phương pháp chung là thêm một trường khóa chỉ số là thứ tự ban đầu của đối tượng. Khi đối sánh, nếu gặp các đối tượng có cùng khóa sắp xếp như nhau thì ta dựa vào thứ tự chỉ số để xếp 02 đối tượng đó theo thứ tự ban đầu.CHƯƠNG VIII: TÌM KiẾMGiới thiệuThuật toán tìm kiếm tuần tựThuật toán tìm kiếm nhị phânCây tìm kiếm số họcCây tìm kiếm cơ sốCHƯƠNG VIII: TÌM KiẾM1. Giới thiệuBài toán. Cho tập N đối tượng, hãy xác định xem có hay không trong tập đó một đối tượng cụ thể.Tập đối tượng cho trước có thể có nhiều thuộc tính có kiểu dữ liệu khác nhau. Thông thường tìm kiếm chỉ căn cứ một hoặc một vài thành phần ( trường). Các thành phần đó gọi là trường khóa tìm kiếm. Quá trình tìm kiếm thường gồm 02 pha:Pha 1: Dựa vào giá trị trường khóa và khóa để xác định đối tượng có giá trị trường khóa bằng với khóa tìm kiếm hặc khẳng định không tìm thấy đối tượng cần tìm;Pha 2: Kết xuất toàn bộ thông tin về đối tượng tìm được.CHƯƠNG VIII: TÌM KiẾMTa chỉ xét pha 1 cho bài toán: Cho một dãy gồm n đối tượng, mỗi đối tượng i ( 1N thì Thông báo không có số hạng nào có giá trị trùng với x, rồi kết thúc.	Bước 6. Quay lại bước 3.k = 2 và N = 10k = 6 và N = 10A5714298112551A5714298112551i12345-----i1234567891011Với i = 5 thì a5 = 2.Với mọi i từ 1 đến 10 không có ai có giá trị bằng 6. Mô phỏng các bước thực hiện của thuật toánNhận xét và đánh giá.Phép toán tích cực là phép so sánh:Trường hợp tốt nhất độ phức tạp là O(1)Trường hợp xấu nhất và trung bình độ phức tạp là O(N)CHƯƠNG VIII: TÌM KiẾM3. Tìm kiếm nhị phânInput: Dãy gồm N số nguyên k1, k2,..., kN đôi một khác nhau và là dãy tăng; số nguyên x.Output: Chỉ số i mà ki = x hoặc thông báo trong dãy không có giá trị trùng với x.Ý tưởng: Sử dụng dãy đã sắp xếp ta tìm cách thu hẹp phạm vi tìm kiếm sau mỗi lần so sánh khóa với số hạng được chọn. aGiua	Giua=[ (N+1)/2].	Nếu kGiua = x thì Giua là chỉ số cần tìm. Nếu kGiua > k thì việc tìm kiếm tiếp theo chỉ xét trên dãy k1, ka2,..., kGiua–1Nếu aGiua x thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7.	Bước 6. Dau  Giua + 1	Bước 7. Nếu Dau > Cuoi thì thông báo dãy không có số hạng có giá trị trùng với x, rồi kết thúc.	Bước 8. Quay lại bước 3.k = 21, N =10k = 25, N =10i12345678910i12345678910A245692122303133A245692122303133Dau166Dau16678Cuoi10107Cuoi1010777Giua586Giua5867aGiua93021aGiua9302122Lượt012Lượt01234Sau hai lượt thì aGiua = k. Vậy chỉ số cần tìm là i = Giua = 6.Tại lượt thứ tư Dau > Cuoi nên kết luận trong dãy A không có toán hạng nào có giá trị là 25 cả.Nhận xét và đánh giáTrường hợp tốt nhất, độ phức tạp tính toán là O(1), trong trường hợp xấu và trung bình là O(lgN) ,Tuy nhiên với dãy chưa được sắp xếp thì cần có chi phí cho việc sắp xếp. 4. Cây tìm kiếm số họcĐịnh nghĩa	Xét dãy khóa k1, k2,kn mỗi giá trị khóa khi đổi ra số nhị phân có z bit, đánh số từ 0 đến z-1 ( phải-trái)	Cây tìm kiếm số học Cây số học chứa các giá trị khóa:Là cây nhị phân, mỗi nút chứa một giá trị khóa;Nút gốc có tối đa 02 cây con; tất cả các khóa có bít cao nhất là 0 nằm ở cây con trái, tất cả các khóa có bít cao nhất là 1 nằm ở cây con phải.Cây con trái và phải cũng có tính chất như vậy.26587111210401010110 6 = 0110 5 = 0101 2 = 0010 7 = 0111 8 = 100010 = 101012 = 110011 = 1011 4 = 01004. Cây tìm kiếm số họcPhép toán tìm kiếmTừ gốc, xét lần lượt các bit của x từ trái sang phải, nếu gặp bit 0 thì đi sang cây con trái, nếu gặp bit 1 thì sang cây con phải;Hoặc đi tới một nút rỗng, tìm kiếm thất bại (không có giá trị x trong dãy khóa);Hặc gặp nút có giá trị bằng x, tìm kiếm thành công.Phép chèn:Tìm xem khóa đã có trong cây hay chưa, nếu chưa có thì thêm nút mới chứa khóa cần chèn và nối nút đó vào cây tại nút rỗng vừa sẽ sang khiến tìm kiếm thất bại.Phép xóaTìm kiếm để xác định nút cần xóa;Tìm trong cây con mà nút cần xóa là nút gốc một nút lá bất kì;Chuyển đổi giá trị của nút lá và nút cần xóa cho nhau;Xóa nút lá.Nhận xét và đánh giáĐộ phức tạp trong các trường hợp là O(min(z,lgN)), trường hợp xấu nhất là O(z) vì chiều cao của cây tìm kiếm số học không quá z+1. 5. Cây tìm kiếm cơ số Cây tìm kiếm cơ số là:Là một cây nhị phân, chỉ có nút lá chứa giá trị khóa và các nút lá đều ở cùng mức z-1;Nút gốc có tối đa là 02 nhánh conMọi nút lá của nhánh con trái đều có bít z-2 là 0 ( đều bắt đầu bằng 00);Mọi nút lá của nhánh con phải đều có bít z-2 là 1 ( đều bắt đầu bằng 01);Tổng quát, với nút mức d đều có tối đa hai nhánh con, mọi nút lá của nhánh con trái đều có bít z-d là 0 và mọi nút lá của nhánh con phải đều có bit z-d là 1Cây tìm kiếm cơ số được khởi tạo gồm 01 nút gốc và nút đó tồn tại trong suốt cả quá trình. CHƯƠNG VIII: TÌM KiẾM5. Cây tìm kiếm cơ sốThao tác tìm kiếm khóa X:Xuất phát từ nút gốc, duyệt dãy bít của x từ trái sang phải ( từ bít z-1 đến bit 0), gặp nút 0 thì rẽ sang trái, gặp nút 1 thì sang phải;Quá trình sẽ dừng lại khi:Hoặc đi tới một nút rỗng, tìm kiếm thất bạiNút ở lá có giá trị trùng nút xThao tác chèn: Thực hiện các thao tác như tìm kiếm, khi gặp một liên kết null ( đi tới nút rỗng) thì tạo nút mới và nối vào theo liên kết đó để có đường đi tiếp.Sau khi duyệt hết các bit của x, dừng lại nút lá của cây và đưa giá trị của x vào nút lá đó. 5. Cây tìm kiếm cơ sốThao tác xóaLặp lại quá trình tìm kiếm;Đánh dấu để biết nút có 02 con cuối cùng (từ nút đó chỉ có một con đường độc đạo đến nút lá);Xóa toàn bộ các nút của đường độc đạo.Giá trị chứa trong các nút cành là vô nghĩa nên sẽ có lãng phí bộ nhớ,Không nhất thiết phải chọn hệ cơ số 2, có thể chọn cơ số lớn hơn để đẩy nhanh tốc độ tìm kiếm nhưng sẽ tốn kém bộ nhớ hơnNhận xét và đánh giáViệc xóa tất cả các nút trên đường độc đạo là để tiết kiệm bộ nhớ ,Hình dáng của cây chỉ phụ thuộc vào các giá trị chứa trong cây,Độ phức tạp trong mọi trường hợp đều là O(z),Chú ý chungHai bài toán sắp xếp và tìm kiếm rất đặc thù của Tin học.Không nên đánh giá các thuật toán sắp xếp cũng như các thuật toán tìm kiếm một cách tổng quát mà còn tùy thuộc vào yêu cầu cụ thể, tính chất dữ liệu cụ thể,..