Kiến trúc máy tính - Phần 12

Thực hiện phân hoạch dãy S cần sắp thành 3 dãy S1, S2, S3. Trong đó: S2 chỉ có một phần tử, tất cả các phần tử của dãy S3 đều phần tử của dãy S2.Tất cả các phần tử của dãy S1 đều ≤ phần tử của dãy S2 Dãy S1, S3 có thể là rỗng Tiếp tục phân hoạch dãy S1 và S3 độc lập theo nguyên tắc trên đến khi dãy cần thực hiện phân hoạch chỉ có một phần tử thì dưng lại. Khi đó ta được dãy các phần tử được sắp....
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - Phần 12 Bài12.CácthuậttoánsắpxếpnhanhO(nlogn) Sắp xếp nhanh – Quick sort Sắp xếp trộn - Merge sort Vun đống – Heap sort 1 SortingChiavàtrịDivideandconquer Chiavàtrịlàphươngphápthiếtkếthuật toántheokiểu: Phânchia:ChiadữliệuđầuvàoScủabàitoán  thành2tậpconrờinhauS1 vàS2 Đệqui:Giảibàitoánvớidữliệuvàolàcáctập  conS1 vàS2 Trị:kếthợpcáckếtquảcủaS1 và S2thànhkết  quảcủaS Trườnghợpcơsởchothuậttoánđệquiở đâylàcácbàitoáncókíchthước0hoặc1 2 SortingSắpxếpnhanh–Quicksort Ý tưởng (sử dụng phương pháp chia và trị): Thực hiện phân hoạch dãy S cần sắp thành 3 dãy S1, S2, S3.  Trong đó: • S2 chỉ có một phần tử, tất cả các phần tử của dãy S3 đều > phần tử của dãy S2. • Tất cả các phần tử của dãy S1 đều ≤ phần tử của dãy S2 • Dãy S1, S3 có thể là rỗng Tiếp tục phân hoạch dãy S1 và S3 độc lập theo nguyên tắc  trên đến khi dãy cần thực hiện phân hoạch chỉ có một phần tử thì dưng lại. Khi đó ta được dãy các phần tử được sắp. 3 SortingThuậttoánsắpxếpQuicksort Từ ýtưởngcủathuậttoán,tacóthểdễdàngxâydựngthuậttoánsắpxếpdướidạngđệquinhưsau:AlgorithmQuickSort(arrayA,i,j);Input:DãycácphầntửA[i],..,A[j]vàhaisốnguyêni,jOutput:DãyA[i],..,A[j]đượcsắp.ifiVídụ 5 SortingVấn đề đặtra ở đâylàphânhoạchdãySnhưthếnào? 6 SortingThuậttoánphânhoạch• Chọnmộtphầntửbấtkỳ 6 12 32 1 3 củadãylàmdãyS2(phần tửnàyđượcgọilàphầntử chốtpivot). 6 3 32 1 12• Thựchiệnchuyểncác phầntửcókhóa≤phầntử chốtvềbêntráivàcác 6 3 1 32 12 phầntử>phầntửchốtvề bênphải,sauđóđặtphần tửchốtvềđúngvịtrícủa nótrongdãy. 1 3 6 32 12 Saukhiphânhoạch 7 SortingChúý • Phần tửchốtcóthể đượcchọnlàmộtphầntử bấtkỳcủadãy. Phầntửchốtcóthểchọnlàphầntử đầu hoặcgiữahoặccuốidãy. Tốtnhấlàchọnphầntửchốtmànólàm cho việc phân hoạch thànhhai dãyS1và S3 cósốphầntửxấpxỉbằngnhau. 8 SortingThuậttoán•PhânhoạchdãygồmcácphầntửA[i],..,A[j] •Chọnphầntửđầudãylàmchốt •Sửdụng2biếnleftvàright: leftchạytừtráisangphảibắtđầutừi. rightchạytừphảisangtráibắtđầutừj BiếnleftđượctăngchotớikhiA[left].Key>A[i].Key hoặcleft>right Biến right được giảm cho tới khi A[right].Key Vídụphânhoạch 10 3 24 1 4 21 54 5 ij ? 10 Sorting ThuậttoánphânhoạchAlgorithmPartition(ArrayA,i,j,&right)Input:DãycácphầntửA[i],..,A[j],2sốnguyêni,jOutput:DãyA[i],..,A[j]đượcphânhoạch,rightlàchỉsốcủa phầntửlàmS2. p←A[i]; left←i;right←j; while(leftVídụSắpxếpdãysố A=… … 10 3 24 1 4 21 54 5 i=1 j=8 ? 12 SortingMôtảquátrìnhSắpxếp 10 3 24 1 4 21 54 5 Quicksort(A,1,8) i=1 j=8iQuicksort(A,1,2) 1 3 4 5 10 21 54 24 i=1j=2 1 3 4 5 10 21 54 24i Quicksort(A,6,5) 1 3 4 5 10 21 54 24 j=5i=6 Quicksort(A,7,8) 1 3 4 5 10 21 54 24iThờigianchạy• Thủtụcpartitionkiểmtratấtcảcácphầntửtrongmảngnhiềunhấtmộtlần,vìvậynómấtthờigiantốiđalàO(n).•Thủtụcpartitionsẽchiaphầnmảngđượcsắpthành2phần.•Mặtkháccầnchialiêntiêpnphầntửthànhhaiphầnthìsốlầnchianhiềunhấtlàlog2nlần.•VậythờigianchạycủathuậttoánQuickSortlàO(nlogn) 16 SortingThuậttoánMergeSortÝtưởng:• GiảsửtacóhaidãyA[i],..,A[k]vàA[k+1],..,A[j]và haidãynàyđãđượcsắp.• ThựchiệntrộnhaidãytrênđểđượcdãyA[i],..,A[j] cũngđượcsắp• DohaidãyA[i],..,A[k]vàdãyA[k+1],..,A[j]đãđược sắpnênviệctrộnhaidãythànhmộtdãyđượcsắplà rấtđơngiản.• Vậytrộnnhưthếnào? 17 Sorting Vídụ:TrộnhaidãysauA … 1 3 24 4 21 54 … i k k+1 j ...