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

CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@agu.edu.vnTRƯỜNG ĐẠI HỌC AN GIANGKHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNGChương 2. TÌM KIẾM VÀ SẮP XẾPNhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTTCác giải thuật tìm kiếm nộiTìm kiếm tuyến tínhTìm kiếm nhị phânCác giải thuật sắp xếp nộiNhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTTNhu cầu?Các giải thuật tìm kiếm nội (Searching Techniques)Tìm kiếm tuyến tính (Sequential Search)Tìm kiếm nhị phân (Linear Search)Mô tả bài toánCho mảng A[1..n] các đối tượng, có các khóa keyChúng ta cần tìm trong mảng có phần tử nào có giá trị bằng x hay không?Lưu ý: Khi cài đặt bằng ngôn ngữ C, do chỉ số mảng trong C bắt đầu từ 0 lên các giá trị chỉ số có thể chênh lệnh so với thuật tóanĐể đơn giản: Dùng mảng các số nguyên làm cơ sở để cài đặt thuật tóan.Tìm kiếm tuyến tính (Sequential Search)Ý tưởng:Đây là giải thuật tìm kiếm cổ điểnThuật tóan tiến hành so sánh x với lần lượt với phần tử thứ nhất, thứ hai,.. của mảng a cho đến khi gặp được phần tủ có khóa cần tìm.Tìm kiếm tuyến tínhGiải thuậtBước 1: i=1; //Bắt đầu từ phần từ đầu tiênBước 2: So sánh a[i].key với x có 2 khả nănga[i].key = x: Tìm thấy, Dừng;a[i].key # x: Sang bước 3;Bước 3: i=i +1; //Xét tiếp phần tử kế tiếp trong mảngNếu i>n: hết mảng, không tìm thấy. DừngNgược lại: lặp lại bước 2Tìm kiếm tuyến tính – ví dụ57991319151119232883032341 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Tìm giá trị x =5, x=46, x=19a46Tìm kiếm tuyến tính – cài đặtCách 1void LinearSearch(int a[], int N, int x) { int i, flag = 0; for(i=0;ix : right = mid -1; a[mid].key Tìm tiếp, lặp lại bước 2Ngược lại: DừngTìm kiếm nhị phân1. (0+15)/2=7; a[7]=19;tìm trong 8..152. (8+15)/2=11; a[11]=32;tìm trong 12..153. (12+15)/2=13; a[13]=37;tím trong 12..125710131315191923282832323741 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Tìm trong mảng a, giá trị 36:a464. (12+12)/2=12; a[12]=32;tìm trong 13..12...nhưng 13>12, => 36 không thấy Tìm kiếm nhị phân5710131315191923282832323741 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Tìm trong mảng a, giá trị 7:a461. (0+15)/2=7; a[7]=19;tìm trong 0..62. (0+6)/2=3; a[3]=13;tìm trong 0..23. (0+2)/2=1; a[1]=7;Kết thúcTìm kiếm nhị phân – cài đặtvoid BinarySearch(int a[],int N, int x) { int left,right,mid, flag = 0; left = 0; right= n-1; while(left a[1] sẽ là phần tử nhỏ nhấtGiả sử ta đã có a[1].key ≤≤ a[i-1].key. Bây giờ ta tìm phần tử có khóa nhỏ nhất trong đọan [i..N]Giả sử tìm thấy a[k], i≤k≤N.Hóan đổi a[k] với a[i], ta được a[1].key ≤≤ a[i].keyLặp lại quá trình trên cho đến khi i=N-1, ta sẽ nhận được mảng a được sắp xếpSelection SortGiải thuậtBước 1: i=1;Bước 2: Tìm phần tử a[k] có khóa nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]Bước 3: Hóan vị a[k] với a[i]Bước 4: Nếu i ≤ N-1 thì i= i+1; lặp lại bước 2.Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị tríSelection SortCho dãy số:   12 2 8 5 1 6 4 15 Selection SortSelection Sort2851641512imin12345670Vị trí nhỏ nhất(0,7)Swap(a[0], a[4])Minh họa thuật toán chọn trực tiếp (Selection Sort)2851264151imin12345670Vị trí nhỏ nhất(1,7)Swap(a[1], a[1])Minh họa thuật toán chọn trực tiếp (Selection Sort)2851264151imin12345670Vị trí nhỏ nhất(2,7)Swap(a[2], a[6])Minh họa thuật toán chọn trực tiếp (Selection Sort)2451268151imin12345670Vị trí nhỏ nhất(3, 7)Swap(a[3], a[3])Minh họa thuật toán chọn trực tiếp (Selection Sort)2451268151imin12345670Vị trí nhỏ nhất(4, 7)Swap(a[4], a[5])Minh họa thuật toán chọn trực tiếp (Selection Sort)2456128151imin12345670Vị trí nhỏ nhất(5,7)Swap(a[5], a[6])Minh họa thuật toán chọn trực tiếp (Selection Sort)2456812151imin12345670Vị trí nhỏ nhất(6, 7)1215Minh họa thuật toán chọn trực tiếp (Selection Sort)Ðánh giá giải thuật Độ phức tạp của thuật toán Selection SortSelection SortCài đặtvoid SelectionSort (int a[], int N){ int k; //chỉ số phần tử nhỏ nhất trong dãy for(int i=0; i= 0) && (a[pos] > x)) //Tìm vị trí chèn x; { a[pos+1] = a[pos]; pos--; } a[pos+1]=x;//chèn x vào }}Insertion SortCài đặt 2: Dành cho các dãy đã sắp xếpvoid BinaryInsertionSort (int a[], int N){ int left, right, mid, i; int x; for(int i=1; i = left ; j--) a[j-1] = a[j]; a[left] = x; //chèn x vào dãy }}PP Đổi chỗ trực tiếp (Interchange Sort) Ý tưởngBắt đầu từ đầu dãy, tìm các phần tử có khóa nhỏ hơn nó, hóan đổi phần tử tìm được và phần tử đầu tiênTiếp tục, thực hiện với phần tử thứ 2,Interchange SortGiải thuậtBước 1: i=1; //bắt đầu từ phần tử đầu dãyBước 2: j =i +1; //tìm các phần tử a[j].key iBước 3: trong khi j ≤ N thực hiệnnếu a[j].key i) thực hiệnnếu a[j].key N -1 : hết dãy, DừngNgược lại: lặp lại bước 2Bubble SortCho dãy số:   12 2 8 5 1 6 4 15Bubble SortBubble SortBubble SortBubble Sort285164151212345670ij1Minh họa Bubble Sort122854615112345670ij2Minh họa Bubble Sort212485615112345670ij4Minh họa Bubble Sort241285615112345670ij5Minh họa Bubble Sort245128615112345670ij6Minh họa Bubble Sort245612815112345670ij8Minh họa Bubble Sort245681215123456781ij1512Minh họa Bubble SortĐộ phức tạp Bubble SortBubble SortCài đặtvoid BubbleSort(int a[], int N) { int i,j; for(i=0; i i; j--) if(a[j] x, với k=j+1..nQuick SortSau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 phần ak x , với k =  j..Nak xQuick SortDãy con thứ 2 đã có thứ tự;Nếu các dãy con 1 và 3 chỉ có 1 phần tử: đã có thứ tự. -> khi đó dãy ban đầu đã được sắp. ak xQuick SortDãy con thứ 2 đã có thứ tự;Nếu các dãy con 1 và 3  có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các dãy con 1, 3 được sắp. Ðể sắp xếp dãy con 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 . ak xQuick SortÝ tưởng: sắp xếp mảng a gồm n phần tử a[1..n]Xác định một phần tử bất kỳ làm chốt (pivot): Mảng được phân họach thành 2 phần bằng cách: a[k]Chuyển tất cả những phần tử có khóa nhỏ hơn chốt sang bên phải chốt (L): a[1]a[k-1] x) j- -Bước 2c: Nếu i xBước 2: Nếu (l x) j--; if (i = a2i+1  {(ai , a2i), (ai ,a2i+1) là các cặp phần tử liên đới } Heap sortHeap có các tính chất sau :Tính chất 1: Nếu al , a2 ,... , ar là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap. Tính chất 2: Nếu a1 , a2 ,... , an là một heap thì phần tử a1 (đầu heap) luôn là phần tử lớn nhất trong heap. Tính chất 3: Mọi dãy al , a2 ,... , ar với 2l > r  là một heap. 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ừngHeap sortTrong đó một phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i+1Phần tử ở mức 0 (nút gốc của cây) luôn là phần tử lớn nhất của dãy. Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớn nhất về đúng vị trí), 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 được bảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả so sánh ở bước hiện tại. Heap sortHeap sortLoại bỏ 8 ra khỏi cây và thế vào các chỗ trống giá trị -∞ để tiện việc cập nhật lại cây : Heap sort – ví dụ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 heap Heap sort – ví dụHeap sort – ví dụGiai đoạn 2: Sắp xếp dãy số dựa trên heap : Heap sort – ví dụthực hiện tương tự cho r=5,4,3,2 ta được 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]Minh họa Heap SortHeap: 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), (ai , a2i+2 ) là các cặp phần tử liên đớiCho 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 Heap Sort281516451212345670l=2Pt liên đới281516451212345670l=1Pt liên đớiMinh họa Heap Sort158216451212345670l=1Lan truyền việc điều chỉnh158516421212345670l=0Pt liên đớiMinh họa Heap Sort1285164215Giai đoạn 2: Sắp xếp dãy số dựa trên Heap12851642151285164152123456701234567012345670r=6Minh họa Heap SortHiệu chỉnh Heap128516415212345670l=2Pt liên đới128516415212345670l=2Pt liên đớiMinh họa Heap Sort128516415212345670l=0Pt liên đới2851641512l=212345670Minh họa Heap Sort2851641512l=212345670Lan truyền việc điều chỉnh5821641512l=212345670Minh họa Heap Sort582164151212345670582161215412345670Thực hiện với r= 5,4,3,2 ta được245681215112345670Heap Sort – cài đặtÐể cài đặt giải thuật Heapsort cần xây dựng các thủ tục phụ trợ:1. Thủ tục hiệu chỉnh dãy al , al+1 ...ar thành heap :2. Hiệu chỉnh dãy a1 , a2 ...aN thành heap : Thủ tục hiệu chỉnh dãy al , al+1 ...ar thành heapGiả sử có dãy al , al+1 ...ar, trong đó đoạn al+1 ...ar, đã là một heap. Ta cần xây dựng hàm hiệu chỉnh al , al+1 ...ar thành heap.Lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i và a2i+1, nếu vi phạm điều kiện quan hệ của heap, thì đổi chỗ ai với phần tử liên đới thích hợp của nó. Lưu ý việc đổi chỗ này có thể gây phản ứng dây chuyền: void Shift (int a[ ], int l, int r )Thủ tục hiệu chỉnh dãy al , al+1 ...ar thành heapvoid Shift (int a[ ], int l, int r ){ int x,i,j;i = l; j =2*i+1; // (ai , aj ), (ai , aj+1) là các phần tử liên đới x = a[i]; while (j= 0)  { Shift(a,l,N-1); l = l -1; }}Heap Sort – cài đặtKhi đó hàm Heapsort có dạng sau :void HeapSort (int a[], int N){ int r; CreateHeap(a,N) r = N-1; // r là vị trí đúng cho phần tử nhỏ nhất while(r > 0) { Hoanvi(a[0],a[r]);  r = r -1; Shift(a,0,r); }}Sắp xếp với độ dài bước giảm dần - Shell sort ShellSort: là một PP cải tiến của PP chèn trực tiếp. Ý tưởng: phâ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 một cách nhanh chóng, Sau đó giảm khoảng cách h để tạo thành các dãy con mới (tạo điều kiện để so sánh một phần tử với nhiều phần tử khác trước đó không ở cùng dãy con với nó) và lại tiếp tục sắp xếp... Thuật toán dừng khi h = 1.Chon h?Shell sortCác bước tiến hành như sau:Bướ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 sort – ví dụCho dãy số:   12 2 8 5 1 6 4 15Giả sử chọn các khoảng cách là 5, 3, 1 h = 5 : xem dãy ban đầu như các dãy con h= 3 : (sau khi đã sắp xếp các dãy con ở bước trước)                                                                                                                                                                                                  h= 1 : (sau khi đã sắp xếp các dãy con ở bước trước)285164151212345670h = (5, 3, 1); k = 3len = 5currjointMinh họa Shell Sort285112415612345670h = (5, 3, 1); k = 3len = 5;Minh họa Shell Sort215511248612345670h = (5, 3, 1); k = 3len = 3currjointMinh họa Shell Sort112621548512345670h = (5, 3, 1); k = 3len = 3currjointjointMinh họa Shell Sort1125215684h = (5, 3, 1); k = 3len = 312345670Minh họa Shell Sortjointcurr112521568412345670h = (5, 3, 1); k = 3len = 1jointjointMinh họa Shell Sortjointcurrjoint451221568112345670h = (5, 3, 1); k = 3len = 1jointjointjointjointjointjointMinh họa Shell Sort245681215112345670Minh họa Shell SortCài đặtGiả sử đã chọn được dãy độ dài h[1], h[2], ..., h[k], thuật toán ShellSort có thể được cài đặt như sau :void ShellSort(int a[], int N, int h[], int k){ int step,i,j; int 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; } //for (2) } //for (1)} //endCảm ơn !