Sắp xếp trộn

Trộn Trực tiếp Giải thuật trộn trực tiếp là phương pháp trộn đơn giản nhất. Việc phân hoạch thành các dãy con đơn giản chỉ là tách dãy gồm n phần tử thành n dãy con. Ðòi hỏi của thuật toán về tính có thứ tự của các dãy con luôn được thỏa trong cách phân hoạch này vì dãy gồm một phân tử luôn có thứ tự.
Nội dung trích xuất từ tài liệu:
Sắp xếp trộnSắpxếptrộn mergesort Tưtưởngtrộn  Có2mảngđãđượcsắpxếpchiềudài N,M  Tạora1mảngchungđượcsắpxếp 2 5 7 8 9 10 13 14 1 3 4 6 11 201 2 3 4 5 6 7 8 9 10 11 13 14 20 Bước1:chọnmincủa2phầntửđầu dãychépquamảngkếtquả Bước2:hủyphầntửmin Bước3:nếuchưađếncuốimảngtrởvề bước1 Nếuđếncuốimảng:chépphầncònlại củamảngkiavàomảngkếtquả 2 5 7 8 9 10 13 14 i=0 1 3 4 6 11 20 j=01 2 5 7 8 9 10 13 14 i=0 1 3 4 6 11 20 j=11 2 2 5 7 8 9 10 13 14 i=1 1 3 4 6 11 20 j=11 2 3 2 5 7 8 9 10 13 14 i=1 1 3 4 6 11 20 j=21 2 3 4 Thựchiệnlầnlượt 2 5 7 8 9 10 13 14 i=1 1 3 4 6 11 20 j=31 2 3 4 2 5 7 8 9 10 13 14 j=7 i=8 1 3 4 6 11 20 J=51 2 3 4 5 6 7 8 9 10 11 13 14 Chépphầncònlạicủamảng2 i=8 20 J=5 j=61 2 3 4 5 6 7 8 9 10 11 13 14 20 A,b,kq  A,b,kq i=j=0  i=j=0 While(i+jSắpxếpbằngphươngphápmergesort Nguyêntắcsắpxếpbằngphéptrộn Ðểsắpxếpdãya1,a2,...,an,giảithuật MergeSortdựatrênnhậnxétsau: Mỗidãya1,a2,...,anbấtkỳđềucóthểcoi nhưlàmộttậphợpcácdãyconliêntiếpmà mồidãyconđềuđãcóthứtự.Vídụdãy12, 2,8,5,1,6,4,15cóthểcoinhưgồm5dãy conkhônggiảm(12);(2,8);(5);(1,6);(4, 15). Dãyđãcóthứtựcoinhưcó1dãycon. mộtcáchtiếpcậnđểsắpxếpdãylàtìmcáchlàmgiảmsốdãy conkhônggiảmcủanó.Ðâychínhlàhướngtiếpcậncủathuật toánsắpxếptheophươngpháptrộn. TrongphươngphápMergesort,mấuchốtcủavấnđềlàcách phânhoạchdãybanđầuthànhcácdãycon.Saukhiphân hoạchxong,dãybanđầusẽđượctáchrathành2dãyphụtheo nguyêntắcphânphốiđềuluânphiên.Trộntừngcặpdãycon củahaidãyphụthànhmộtdãyconcủadãybanđầu,tasẽnhân lạidãybanđầunhưngvớisốlượngdãyconítnhấtgiảmđimột nửa.Lặplạiquitrìnhtrênsaumộtsốbước,tasẽnhậnđược1 dãychỉgồm1dãyconkhônggiảm.Nghĩalàdãybanđầuđã đượcsắpxếp.TrộnTrựctiếp Giảithuậttrộntrựctiếplàphươngpháptrộn đơngiảnnhất.Việcphânhoạchthànhcác dãyconđơngiảnchỉlàtáchdãygồmnphần tửthànhndãycon.Ðòihỏicủathuậttoánvề tínhcóthứtựcủacácdãyconluônđượcthỏa trongcáchphânhoạchnàyvìdãygồmmột phântửluôncóthứtự.Cứmỗilầntáchrồi trộn,chiềudàicủacácdãyconsẽđượcnhân đôi.Thuậttoán Cácbướcthựchiệnthuậttoánnhưsau: Bước1://Chuẩnbị k=1;//klàchiềudàicủadãycontrongbước hiệnhành Bước2: Táchdãya1,a2,.,anthành2dãyb,ctheo nguyêntắcluânphiêntừngnhómkphầntử: b=a1,…,ak,a2k+1,.,a3k,. c=ak+1,.,a2k,a3k+1,.,a4k,.Thuậttoán(tt) Bước3: Trộntừngcặpdãycongồmkphầntử của2dãyb,cvàoa. Bước4: k=k*2; Nếuk Vídụ  Sắpxếpdãysố  3,5,1,6,12,7,4,10,2,83 5 1 6 12 7 4 10 2 8 3 5 1 6 12 7 4 10 2 8K=1 3 1 12 4 2 5 6 7 10 8 3 5 1 6 7 12 4 10 2 8 3 5 1 6 7 12 4 10 2 8K=2 3 5 7 12 2 8 1 6 4 10 1 3 5 6 4 7 10 12 2 8 1 3 5 6 4 7 10 12 2 8K=4 1 3 5 6 2 8 4 7 10 12 ...