Bài giảng Cấu trúc dữ liệu và giải thuật 1 - Chương 2: Tìm kiếm và sắp xếp nội

CHƯƠNG 2TÌM KIẾM VÀ SẮP XẾP NỘINội Dung Các giải thuật tìm kiếm nội1. Tìm kiếm tuyến tính2. Tìm kiếm nhị phân Các giải thuật sắp xếp nội 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble SortNội Dung (Tt)4. Chèn trực tiếp – Insertion Sort5. Chèn nhị phân – Binary Insertion Sort6. Shaker Sort7. Shell Sort8. Heap Sort 9. Quick Sort10. Merge Sort11. Radix SortBài Toán Tìm KiếmCho danh sách có n phần tử a0, a1, a2, an-1. Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính.Tìm phần tử có khoá bằng X trong mảngGiải thuật tìm kiếm tuyến tính (tìm tuần tự)Giải thuật tìm kiếm nhị phân Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C.Tìm Kiếm Tuyến TínhÝ tưởng : So sánh X lần lượt với phần tử thứ 1, thứ 2,của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.Các bước tiến hànhBước 1: Khởi gán i=0;Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng + a[i] == x tìm thấy x. Dừng; + a[i] != x sang bước 3;Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng Nếu i==N: Hết mảng. Dừng; Ngược lại: Lặp lại bước 2;Thuật Toán Tìm Kiếm Tuyến Tính Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:int LinearSearch(int a[],int n, int x){ int i=0; while((iai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]Nếu Xx : Right= mid-1; a[mid] không tìm thấy X=-171234560RMMinh Họa Thuật Toán Tìm Nhị Phân (tt)Bài Toán Sắp XếpCho danh sách có n phần tử a0, a1, a2, an-1. Sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số tiêu chuẩn nào đó dựa trên thông tin lưu tại mỗi phần tử, như:Sắp xếp danh sách lớp học tăng theo điểm trung bình.Sắp xếp danh sách sinh viên tăng theo tên.Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách trên trong bộ nhớ chính.Bài Toán Sắp Xếp (tt)a: là dãy các phần tử dữ liệuĐể sắp xếp dãy a theo thứ tự (giả sử theo thứ tự tăng), ta tiến hành triệt tiêu tất cả các nghịch thế trong a.Nghịch thế: Cho dãy có n phần tử a0, a1,,an-1Nếu iaj Đánh giá độ phức tạp của giải thuật, ta tínhCss: Số lượng phép so sánh cần thực hiệnCHV: Số lượng phép hoán vị cần thực hiệna[0], a[1] là cặp nghịch thế34348Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortCác Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortĐổi Chỗ Trực Tiếp – Interchange SortÝ tưởng: Xuất phát từ đầu dãy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy.Các Bước Tiến HànhBước 1: i = 0; // bắt đầu từ đầu dãy Bước 2: j = i+1; //tìm các nghịch thế với a[i] Bước 3: Trong khi j i) thực hiện: Nếu a[j]i ; j --) if(a[j]r là đoạn cần được sắp xếp k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng // để làm cơ sơ thu hẹp đoạn l->rBước 2: Bước 2a: j=r; //đẩy phần tử nhỏ về đầu mảng Trong khi j>l nếu a[j]a[j+1] thì {Doicho(a[j],a[j+1]); k=j;} j++; r=k; //loại phần tử đã có thứ tự ở cuối dãy Bước 3: Nếu l left; j --)                if (a[j] a[j+1]) {Swap(a[j], a[j-1]);k = j; }                            right = k; }}Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortChèn Trực Tiếp – Insertion SortGiả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự. Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a0 , a1,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 = 0)&&(a[pos] > x)) {//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới a[pos+1] = a[pos]; pos--; } a[pos+1] = x; // chèn x vào dãy }}Minh Họa Thuật Toán Insertion Sort2851641512123456702851641512ix12345670pos2Minh Họa Thuật Toán Insertion SortInsert a[1] into (0,0)1285164152ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[2] into (0, 1)88125164152ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[3] into (0, 2)55812164152ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[4] into (0, 3)12581264151ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[5] into (0, 4)62568124151ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[6] into (0, 5)42456812151ix12345670posMinh Họa Thuật Toán Insertion SortInsert a[8] into (0, 6)152456812151pos12345670Minh Họa Thuật Toán Insertion SortĐộ Phức Tạp Của Insertion SortCác Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortChèn Nhị Phân – Binary Insertion Sort void BInsertionSort(int a[],int n ){ int l,r,m,i; int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=1 ; i=l ; j--) a[j+1] = a[j];// dời các phần tử sẽ đứng sau x a[l] = x; // chèn x vào dãy }}Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortShell SortCải tiến của phương pháp chèn trực tiếp Ý tưởng:Phân hoạch dãy thành các dãy conSắp xếp các dãy con theo phương pháp chèn trực tiếp Dùng phương pháp chèn trực tiếp sắp xếp lại cả dãy.Shell SortPhân chia dãy ban đầu thành những dãy con gồm các phần tử ở cách nhau h vị tríDãy ban đầu : a1, a2, ..., an được xem như sự xen kẽ của các dãy con sau : Dãy con thứ nhất : a1 ah+1 a2h+1 ... Dãy con thứ hai : a2 ah+2 a2h+2 ... ....Dãy con thứ h : ah a2h a3h ... Shell SortTiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối Giảm khoảng cách h để tạo thành các dãy con mới Dừng khi h=1Shell Sort Giả sử quyết định sắp xếp k bước, các khoảng cách chọn phải thỏa điều kiện : hi > hi+1 và hk = 1 hi = (hi-1 - 1)/3 và hk = 1, k = log3n-1 Ví dụ :127, 40, 13, 4, 1 hi = (hi-1 - 1)/2 và hk = 1, k = log2n-1 Ví dụ : 15, 7, 3, 1 Shell Sorth có dạng 3i+1: 364, 121, 40, 13, 4, 1Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1.Shell SortBước 1: Chọn k khoảng cách h[1], h[2], ..., h[k]; i = 1;Bước 2: Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp;Bước 3 : i = i+1;          Nếu i > k : Dừng          Ngược lại : Lặp lại Bước 2.       Shell SortCho dãy số a: 12 2 8 5 1 6 4 15Giả sử chọn các khoảng cách là 5, 3, 1 Shell Sorth = 5 : xem dãy ban đầu như các dãy conShell Sorth = 3 : (sau khi đã sắp xếp các dãy con ở bước trước)Shell Sorth = 1 : (sau khi đã sắp xếp các dãy con ở bước trước Shell SortShell Sortvoid ShellSort(int a[],int n, int h[], int k){ int step,i,j, x,len; for (step = 0 ; step =0)// sắp xếp dãy con chứa x { // bằng phương pháp chèn trực tiếp a[j+len] = a[j]; j = j - len; } a[j+len] = x; } }}285164151212345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 5currjoint285112415612345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 5;215511248612345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 3currjoint112621548512345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 3currjointjoint1125215684Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 312345670jointcurr112521568412345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 1jointjointjointcurrjoint451221568112345670Shell Sort – Ví Dụh = (5, 3, 1); k = 3len = 1jointjointjointjointjointjoint2456812151Shell Sort – Ví Dụ12345670Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortThuật Toán Sắp Xếp Heap SortHeap Sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng đượcĐể làm được điều này Heap sort thao tác dựa trên cây.Thuật Toán Sắp Xếp Heap SortCho dãy số : 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 a[6]1228516415a[0]a[1]a[2]a[3]a[4]a[5]a[7]Thuật toán sắp xếp Heap SortỞ cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đó phần tử ở nút gốc là phần tử lớn nhất.Nếu loại bỏ gốc ra khỏi cây, thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toàn.Bước kế tiếp có thể sử dụng lại kết quả so sánh của bước hiện tại.Vì thế độ phức tạp của thuật toán O(nlog2n)Các Bước Thuật ToánGiai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heapGiai đoạn 2: Sắp xếp dãy số dựa trên heap:Bước 1:Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy:  r = n-1; Swap (a1 , ar );Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1; Hiệu chỉnh phần còn lại của dãy từ a1 , a2 ... ar thành một heap.Bước 3: Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2 Ngược lại : DừngMinh Họa Thuật ToánHeap: Là một dãy các phần tử al, al+1 ,... , ar  thoả các quan hệ với mọi i  [l, r]:ai  a2i+1ai  a2i+2 // (ai , a2i+1), (ai , a2i+2 ) là các cặp phần tử liên đới Cho dãy số : 12 2 8 5 1 6 4 15Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành Heap285164151212345670l=3Pt liên đớiMinh Họa Thuật Toán281516451212345670l=2Pt liên đới281516451212345670l=1Pt liên đớiMinh Họa Thuật Toán158216451212345670l=1Lan truyền việc điều chỉnh158516421212345670l=0Pt liên đớiMinh Họa Thuật Toán1285164215Giai đoạn 2: Sắp xếp dãy số dựa trên Heap12851642151285164152123456701234567012345670r=6Minh Họa Thuật ToánHiệu chỉnh Heap128516415212345670l=2Pt liên đới128516415212345670l=2Pt liên đớiMinh Họa Thuật Toán128516415212345670l=0Pt liên đới2851641512l=212345670Minh Họa Thuật Toán2851641512l=212345670Lan truyền việc điều chỉnh5821641512l=212345670Minh Họa Thuật Toán582164151212345670582161215412345670Thực hiện với r= 5,4,3,2 ta được245681215112345670Cài Đặt Thuật ToánHiệu chỉnh al, al+1,..,ar thành Heapvoid shift(int a[],int l,int r){ int x,i,j; i=l; j=2*i+1; x=a[i]; while(j=0) { shift(a,l,n-1); l=l-1; } }Cài Đặt Thuật ToánHàm HeapSort void HeapSort(int a[],int n) { int r; CreateHeap(a,n); r=n-1; while(r>0) { Swap(a[0],a[r]);//a[0] la nút gốc r--; if(r>0) shift(a,0,r); }}Các Thuật Toán Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix SortQuick Sort Ý tưởng:Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần :Phần 1: Gồm các phần tử có giá trị bé hơn xPhần 2: Gồm các phần tử có giá trị bằng x Phần 3: Gồm các phần tử có giá trị lớn hơn x với x là giá trị của một phần tử tùy ý trong dãy ban đầu. Quick Sort - Ý TưởngSau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn:1. ak ≤ x , với k = 1 .. j2. ak = x , với k = j+1 .. i-13. ak  x , với k = i..NĐoạn thứ 2 đã có thứ tự. Nếu các đoạn 1 và 3 chỉ có 1 phần tử : đã có thứ tự  khi đó dãy con ban đầu đã được sắp. Quick Sort – Ý TưởngĐoạn thứ 2 đã có thứ tự. Nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp. Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày Quick Sort – Ý TưởngGiải Thuật Quick SortBước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử Kết thúc; //dãy đã được sắp xếpBước 2: Phân hoạch dãy aleft aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright Đoạn 1  x Đoạn 2: aj+1.. ai-1 = x Đoạn 3: ai.. aright  xBước 3: Sắp xếp đoạn 1: aleft.. ajBước 4: Sắp xếp đoạn 3: ai.. arightGiải Thuật Quick SortBước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc ( l ≤ k ≤ r): x = a[k]; i = l; j = r; Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ : Bước 2a : Trong khi (a[i]x) j--; Bước 2c : Nếu i x) j--; if(i 0)&&(nc>0)) { kb=min(k,nb); kc=min(k,nc); if(b[pb+ib]b) return b; else return a;}Độ phức tạp của Merge SortSố lần lặp của Bước 2, 3 là log2n do sau mỗi lần lặp giá trị k tăng gấp đôi. Chi phí thực hiện ở bước 2 và 3 tỉ lệ thuật với n. Do dó chi phí của dãy thuật MergeSort là O(nlog2n)Các Thuật Toán Sắp Xếp1. Đổi chỗ trực tiếp – Interchange Sort2. Nổi bọt – Bubble Sort3. Shaker Sort4. Chèn trực tiếp – Insertion Sort5. Chèn nhị phân – Binary Insertion Sort6. Shell Sort7. Chọn trực tiếp – Selection Sort8. Quick Sort9. Merge Sort10. Heap Sort 11. Radix SortSắp Xếp Theo Phương Pháp Cơ Số Radix Sort Radix Sort là một thuật toán tiếp cận theo một hướng hoàn toàn khác. Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó Radix Sort còn có tên là Postman’s Sort. Radix Sort không hề quan tâm đến việc so sánh giá trị của phần tử mà bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử. Sắp Xếp Theo Phương Pháp Cơ Số Radix Sort Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, ..., an, giải thuật Radix Sort thực hiện như sau:Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, ..., an là một số nguyên có tối đa m chữ số.Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, .Sắp Xếp Theo Phương Pháp Cơ Số Radix Sort Bước 1 :// k cho biết chữ số dùng để phân loại hiện hànhk = 0; // k = 0: hàng đơn vị; k = 1: hàng chục; Bước 2 : //Tạo các lô chứa các loại phần tử khác nhauKhởi tạo 10 lô B0, B1, , B9 rỗng; Sắp Xếp Theo Phương Pháp Cơ Số Radix SortBước 3 : For i = 1 .. n doĐặt ai vào lô Bt với t: chữ số thứ k của ai;Bước 4 : Nối B0, B1, , B9 lại (theo đúng trình tự) thành a.Bước 5 : k = k+1;Nếu k < m thì trở lại bước 2. Ngược lại: DừngSắp Xếp Theo Phương Pháp Cơ Số Radix Sort Sắp Xếp Theo Phương Pháp Cơ Số Radix SortSắp Xếp Theo Phương Pháp Cơ Số Radix SortSắp Xếp Theo Phương Pháp Cơ Số Radix SortSắp Xếp Theo Phương Pháp Cơ Số Radix SortBài TậpNhập một dãy số nguyên n phần tử.Sắp xếp lại dãy sao cho: số nguyên dương đầu ở đầu dãy và theo thứ tự giảm.số nguyên âm tăng ở cuối dãy và theo thứ tự tăng.số 0 ở giữa.Lưu ý: Không dùng đổi chỗ trực tiếp.