Một số thuật toán cơ bản

CHƯƠNG II. MỘT SỐ THUẬT TOÁN CƠ BẢN11/16/20201BÀI 1: CÁC THUẬT TOÁN SẮP XẾP1. Giới thiệu.2. Sắp xếp bằng lựa chọn (Selection);3. Sắp xếp chèn (Insertion);4. Sắp xếp nổi bọt (Bubble);5. Sắp xếp nhanh (Quicksort);6. Tính ổn định của thuật toán sắp xếp.11/16/20202BÀI 1. CÁC THUẬT TOÁN SẮP XẾP1. Giới thiệuSắp xếp là bố trí lại vị trí các phần tử của một tập đối tượng theo một trật tự nào đó. Ví dụ, việc sắp xếp các từ trong từ điển theo bảng chữ cái, sắp xếp dữ liệu trong máy tính, sắp xếp kết quả điểm thi tuyển sinh từ cao đến thấp, sắp xếp danh sách sinh viên theo thứ tự ABC,11/16/20203BÀI 1. CÁC THUẬT TOÁN SẮP XẾP1. Giới thiệuYêu cầuTập đối tượng có thể thuộc nhiều kiểu dữ liệu khác nhau.Thông thường yêu cầu sắp xếp chỉ căn cứ vào các thành phần gọi là trường khóa sắp xếp ( gọi tắt là trường khóa). Quá trình sắp xếp sẽ dựa vào giá trị của trường khóa.Thực hiện qua hai phaPha 1: Dựa vào giá trị trường khóa và yêu cầu sắp xếp ta xác định vị trí của mỗi đối tượng trong tập sau khi sắp xếp.Pha 2: Chuyển toàn bộ thông tin của đối tượng (STRUCT) về đúng vị trí tương ứng đã xác định trong Pha 1.11/16/20204BÀI 1. CÁC THUẬT TOÁN SẮP XẾP1. Giới thiệuTổng quát Cho dãy K gồm n giá trị khóa k1, k2,, kn. Giữa hai khóa có quan hệ “1) and (a[j] x } L3 = { y in L : y = x } quicksort(L1) quicksort(L2) return concatenation of L1, L3, and L2 } }11/16/202022BÀI 1. CÁC THUẬT TOÁN SẮP XẾP5. Sắp xếp nhanh11/16/202023BÀI 1. CÁC THUẬT TOÁN SẮP XẾP5. 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 NlogN 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. Khử đệ quy. Cũng có thể sử dụng phương pháp chọnToàn bộ quá trình đòi hỏi khoảng: N + N/2+ N/4+.. = 2N phép so sánh.11/16/202024BÀI 1. CÁC THUẬT TOÁN SẮP XẾP 6. 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ật 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.11/16/202025BÀI 1. CÁC THUẬT TOÁN SẮP XẾP 7. Bài tậpCác bài tập từ 1 đến 4 trang 22 (Giáo trình Nhập môn thuật toán).11/16/202026BÀI 2. CÁC THUẬT TOÁN TÌM KiẾMGiới thiệu.Thuật toán tìm kiếm tuần tự.Thuật toán tìm kiếm nhị phân.11/16/202027BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM1. Giới thiệuTập đối tượng cho trước có thể có nhiều kiểu dữ liệu khác nhau. Thông thường yêu cầu 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.11/16/202028BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM 1. Giới thiệuTa 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 dãy khóa 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.11/16/202032BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM2. Tìm kiếm tuần tựProcedure SerialSearch(A,x){Found:=false;For i:=1 to n doIf a[i]=x then found:=true; exit;}11/16/202033BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM2. Tìm kiếm tuần tựNhậ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)11/16/202034BÀI 2. CÁC THUẬT TOÁN 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 không có số hạng nào của dãy có giá trị trùng với x.11/16/202035BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM3. Tìm kiếm nhị phânÝ 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]. 11/16/202036BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM3. Tìm kiếm nhị phânNế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.11/16/202038BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM3. Tìm kiếm nhị phânCho mảng A đã được sắp xếp tăngTìm phần tử b=25 có xuất hiện trong A hay không ?So sánh: b=25 > ; chứng tỏ b không thể xuất hiện trong phạm vi A[1] đến A[5]51818142227313945L=1R=10N=10L+R div 2 = 51818L=6R=1011/16/202039BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM3. Tìm kiếm nhị phânCho mảng A đã được sắp xếp tăngTìm phần tử b=25 có xuất hiện trong A hay không ?So sánh: b=25 ; chứng tỏ b không thể xuất hiện trong phạm vi A[6] đến A[6]51818142227313945L=R=7R=7N=10L+R div 2 =62222L=611/16/202041BÀI 2. CÁC THUẬT TOÁN TÌM KiẾM3. Tìm kiếm nhị phânCho mảng A đã được sắp xếp tăngTìm phần tử b=25 có xuất hiện trong A hay không ?So sánh: b=25 b then L:=Mid+1; If Xb thì ucln(a,b)= ucln(a-b,b), thuật toán được mô tả như sau:Function ucln(a,b); {giả thiết b0} if(a=b)or(b=1)then ucln:=b {phần cơ sở} else if(ab)and(b1)doIf(a<b)thent:=a; a:=b; b:=t;a:=a-b;ucln:=b;11/16/202069BÀI 3. ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY 5. Khử đệ quyVí dụ 2: khử đệ quy của thuật toán tìm số FIBO thứ n.Thuật toán được mô tả như sau:Function Fibo(n);x:=0; y:=1; k:=2;while(k<=n) do t:=y; y:=x+y; x:=t;k:=k+1;Return y;11/16/202070BÀI 3. ĐỆ QUY VÀ THUẬT TOÁN ĐỆ QUY 6. Bài tậpMột số bài tập trang 33,34 (Giáo trình Nhập môn thuật toán).11/16/202071