Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Ngọc Như Loan

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Các giải thuật tìm kiếm và sắp xếp" cung cấp cho người học các kiến thức: Định nghĩa giải thuật tìm kiếm, bài toán, tìm kiếm tuần tự,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Ngọc Như LoanGV:ĐỗNgọcNhưLoanĐịnhnghĩagiảithuậttìmkiếm Input:mộtdãynđốitượng(a1,a2,....,an)và mộtđốitượngk Output:làmộtgiátrịlogictruenếucóktrong dãyhoặcfalsenếungượclại DùngmảnghoặcDSLKđểbiểudiễndãyđối tượng Phầnnàydùngmảngmộtchiều(cácđối tượnglàsố)BàitoánYêu cầu: Cho dãy số nguyên a chứa các số đôimộtkhácnhau.Quy ướcvịtrícủaphầntửđầutiênlà 0. Tìm vị trí xuất hiện của phần tử có giá trị ktrong dãy a hoặc đưa ra 1 nếu không có phần tửnàobằngk.DữliệuvàotừfileTIMKIEM.INPcódạng: Dòngđầulàsốnguyênnvàk DòngthứhaigồmnsốKết quả ra file TIMKIEM.OUT có dạng: vị trí của ktrongdãysố.Vídụ:TIMKIEM.INP68Tìmkiếmtuầntự(Linearsearch)Ýtưởng:Duyệttuầntựtừđầumảng,kếthợpsosánhgiátrịcácphầntửcủamảngvớikđểxácđịnhcóhaykhôngphầntửkk=8 9 2 8 3 1 4 i=0 9 2 8 3 1 4 i=1 9 2 8 3 1 4 i=2 Đãtìm được Output 2boolSearch(intA[MAX],intn,intk)//mảngcónsốnguyên{ for(inti=0;iĐỘPHỨCTẠP Tốtnhất:T(n)=O(1) Xấunhất:T(n)=O(n) Trungbình:T(n)=O(n) BàitoánYêu cầu: Cho dãy số nguyên a chứa các số đôimộtkhácnhauđãsắpxếptăngdần.Quyướcvịtrícủaphầntửđầutiênlà0.Tìmvịtríxuấthiệncủaphầntửcógiátrịktrongdãyahoặcđưara1nếukhôngcóphầntửnàobằngk.DữliệuvàotừfileTIMKIEM.INPcódạng: Dòngđầulàsốnguyênnvàk DòngthứhaigồmnsốKếtquảrafileTIMKIEM.OUTcódạng:vịtrícủaktrongdãysố.Vídụ:TIMKIEM.INP BàitoánYêu cầu: Cho dãy số nguyên a chứa các số đôimộtkhácnhau đãsắpxếptăngdần.Quy ướcvịtrí của phần tử đầu tiên là 0. Tìm vị trí xuất hiệncủaphầntửcógiátrịktrongdãyahoặcđưara1nếukhôngcóphầntửnàobằngk.DữliệuvàotừfileTIMKIEM.INPcódạng: Dòngđầulàsốnguyênnvàk DòngthứhaigồmnsốKếtquảrafileTIMKIEM.OUTcódạng:vịtrícủaktrongdãysố.Vídụ:TIMKIEM.INPTìmkiếmnhịphân(binarysearch)ÁpdụngtrongtrườnghợpdãyđãđượcsắpxếpÝtưởng:Tìmktạiđiểmgiữacủamảng,nếuchưatìmthấythìthìtìmbêntráihoặcbênphải(nhịphân)củamảng(sovớiđiểmgiữa)k=8 1 2 3 4 8 9 left=0,right=5,mid=2 1 2 3 4 8 9 left=3,right=5,mid=4 Đãtìm Output được 4k=3 1 2 3 4 7 9 10 12 left=0,right=7,mid=3 1 2 3 4 7 9 10 12 left=0,right=2,mid=1 1 2 3 4 7 9 10 12 left=2,right=2,mid=2 Output Đãtìm 2 được Begin Nhậpdãysố, k left=0,right=n–1 leftk mid left=mid+1 right=mid1EndboolBinarySearch(intA[MAX],intn,intk){ inti=0,j=n1,m; while(iA[m])i=m+1; elsej=m1; } returnfalse;}ĐỘPHỨCTẠP Tốtnhất:T(n)=O(1) Xấunhất:T(n)=O(log2n) Trungbình:T(n)=O(log2n)ĐỊNHNGHĨAGIẢITHUẬTSẮPXẾPCácgiảithuậtsắpxếp InsertionSort,SelectionSort,BubbleSort QuickSort,HeapSort,MergeSort CountingSort,BucketSort BàiToánYêucầu: Chodãysốnguyêngồmnphầntử.Hãysắpxếpdãysốtheothứtựtăngdần.DữliệuvàotừfileSAPXEP.INPgồm2dòng:+Dòng1chứasốnguyêndươngn(nChọntrựctiếp(selectionsort) ChọnphầntửnhỏnhấttrongA[i…n]vàhoán vịchophầntửđầutiênA[i] Bắtđầuvớii=1vàlặplạichođếnkhii=n13 5 2 1 7 i=1 k=41 5 2 3 7 i=2 k=31 2 5 3 7 i=3 k=41 2 3 5 7 i=4 k=41 2 3 5 7 ...