Các giải thuật sắp xếp nội

Ý tưởng: mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành Xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử.
Nội dung trích xuất từ tài liệu:
Các giải thuật sắp xếp nội CÁCGIảITHUậT SắPXếPNộI1ĐịNHNGHĨABÀITOÁNSắPXếP Sắpxếplàquátrìnhxửlýmộtdanhsáchcác phầntử(hoặccácmẫutin)đểđặtchúngtheomột thứtựthỏamãnmộttiêuchuẩnnàođódựatrên nộidungthôngtinlưugiữtạimỗiphầntử 2KHÁINIệMNGHịCHTHế Kháiniệmnghịchthế: Xétmộtmảngcácsốa ,a ,…a 0 1 n Nếucóia ,thìtagọiđólàmộtnghịch i j thế. Mảngchưasắpxếpsẽcónghịchthế. Mảngđãcóthứtựsẽkhôngchứanghịchthế. a ≤a ≤…≤a 0 1 n 3CÁCPHƯƠNGPHÁPSắPXếPTHÔNGDụNG Selectionsort Phứctạphơn •Shellsort Insertionsort Hiệuquảcao •Heapsort Interchangesort •Quicksort Bubblesort •Mergesort Shakersort •Radixsort BinaryInsertionsort •… Lớpthuậttoán Đơngiản, khác Chiphícao 4 PHƯƠNGPHÁP CHọNTRựCTIếP5 Selectionsort Vịtrí58phầntửnhỏnhấtlà: 12 5 1 6 3 7 4 10 2 0 1 2 3 4 5 6 7 8 Min=a For(j=a+1;jPHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT Mảngcóthứtựthìa =min(a ,a ,…,an1) i i i+1 Ýtưởng:môphỏngmộttrongnhữngcách sắpxếptựnhiênnhấttrongthựctế:  ChọnphầntửnhỏnhấttrongNphầntửban đầu,đưaphầntửnàyvềvịtríđúnglàđầudãy hiệnhành  XemdãyhiệnhànhchỉcònN1phầntửcủa dãybanđầu,bắtđầutừvịtríthứ2;lặplạiquá trìnhtrênchodãyhiệnhành...đếnkhidãy hiệnhànhchỉcòn1phầntử. 7PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT Bước1:i=1; Bước2:Tìmphầntửa[min]nhỏnhấttrong dãyhiệnhànhtừa[i]đếna[N] Bước3:Nếumin≠i,Hoánvịa[min]vàa[i] Bước4:Nếui≤N1thìi=i+1;LặplạiBước2 Ngượclại:Dừng.//N1phầntửđãnằmđúngvị trí. 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT Vídụ:sắpxếpdãysốsau 3,5,1,6,12,7,4,10,2 3 5 1 6 12 7 4 10 2 9PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 3 5 1 6 12 7 4 10 2 i=0 min=2 1 5 3 6 12 7 4 10 2 10 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 5 3 6 12 7 4 10 2 i=1 min=8 1 2 3 6 12 7 4 10 5 11 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 6 12 7 4 10 5 i=min=2 1 2 3 6 12 7 4 10 5 12 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 6 12 7 4 10 5 i=3 min=6 1 2 3 4 12 7 6 10 5 13 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 4 12 7 6 10 5 i=4 min=8 1 2 3 4 5 7 6 10 12 14 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 4 5 7 6 10 12 i=5 min=6 1 2 3 4 5 6 7 10 12 15 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 4 5 6 7 10 12 i=min=6 1 2 3 4 5 6 7 10 12 16 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 4 5 6 7 10 12 i=min=7 1 2 3 4 5 6 7 10 12 17 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT 1 2 3 4 5 6 7 10 12 i=min=8 1 2 3 4 5 6 7 10 12 18 0 1 2 3 4 5 6 7 8PHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORTvoidSelectionSort(){ intmin;//chỉsốphầntửnhỏnhấttrongdãyhiệnhành for(inti=0;iPHƯƠNGPHÁPCHọNTRựCTIếPSELECTIONSORT Đánhgiágiảithuật: Ởlượtthứi,cần(ni)lầnsosánhđểxác địnhphầntửnhỏnhấthiệnhành. Sốlượngphépsosánhkhôngphụthuộc vàotìnhtrạngcủadãysốbanđầu. Trongmọitrườnghợp,sốlầnsosánhlà: n −1 n(n − 1) ∑n −i = 2 i =1 20 ...