Giải thuật sắp xếp dữ liệu

tin học ngày càng phát triển, các yêu cầu của thực tiễn ngày càng đa dạng. Điều đó đòi hỏi phải thiết kế các giải thuật giải quyết một cách hiệu quả nhất vấn đề đặt ra. Sắp xếp (sort) là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng một vai trò rất quan trọng trong việc tìm kiếm dữ liệu. Chẳng hạn, chúng ta thử hình dung xem một cuốn từ điển nếu các từ không được sắp xếp thứ tự mà người ta vẫn thường làm sẽ khó khăn thế nào trong việc tra cứu các từ. Trong lĩnh vực kinh tế việc sắp lại càng quan trọng. Với sự bùng nổ của công nghệ thông tin đã xuất hiện nhiều ngôn ngữ lập trình ví dụ như foxpro, pascal,C+,C++,...Trong đó, ngôn ngữ lập trình cấp cao pascal là một ngôn ngữ có định kiểu mạnh mẽ, gần gũi với ngôn ngữ tự nhiên và được nhiều người biết đến. Đó chính là lý do mà nhóm chúng tôi đã lựa chọn ngôn ngữ này để sử dụng cho bài toán sắp xếp. Để giải quyết một bài toán sắp xếp ta có rất nhiều cách như: sắp xếp theo kiểu lựa chọn, sắp xếp theo kiểu đổi chỗ, sắp xếp theo kiểu vun đống,... Thông qua ngôn ngữ lập trình pascal nhóm chúng tôi đã đưa ra một số thuật toán sắp xếp cơ bản. Mong được sự ủng hộ của thầy cô và các bạn. Giới thiệu và phân tích bài toán. 1)Tên đề tài Xây dựng chương trình cài đặt các thuật toán: - Sắp xếp kiểu lựa chọn - Sắp xếp kiểu đổi chỗ - Sắp xếp kiểu vun đống - Sắp xếp kiểu thêm dần - Sắp xếp kiểu phân đoạn - Sắp xếp kiểu hoà nhập hai đường 2) Thời gian thực hiện chương trình - Từ ngày 16/03/2006 - Đến ngày 16/04/2006 3) Mục đích của đề tài Đề tài này nhằm các mục đích nghiên cứu các giải thuật sắp xếp, cài đặt chương trình chạy cụ thể cho từng giải thuật, phân tích tính hiệu quả và phạm vi ứng dụng của từng giải thuật. Và như vậy với mỗi bài toán cụ thể, ta có thể ứng dụng giải thuật phù hợp nhất cho bài toán để xửu lý dữ liệu một cách hoàn hảo nhất. I. Sắp xếp kiểu chèn ( thêm dần ) – insertion sort 1. Lý thuyết liên quan . a. Cấu trúc dữ liệu: - Cấu trúc kiểu mảng. b. Giải thuật: * Ý tưởng giải thuật: - Ban đầu coi dãy khoá chỉ có dãy khoá K1 đã được sắp xếp, khi xét them dãy khóa K2, ta phải so sánh K2 với K1 để tìm chỗ thích hợp chèn K2 vào. Dãy K1 và K2 đã được sắp xếp sau đó xét them K3 ta phải so sánh K1 và K2 để tìm chỗ chèn K3 vào cho đến Kn được chèn vào đúng chỗ. Khi đó thuật toán kết thúc * Giải thuật: Procedure Insert_sort (K,n) { Để đảm bảo việc chèn được thực hiện ngay từ khoá đầu tiên ta đưa vào dãy khoá sắp xếp một khoá giả có giá trị nhỏ hơn tất cả các khóa thực sự trong dãy và đứng ở đầu dãy K[0]= - ; x=K[i] X: lưu trữ khoá đang xét ở lượt thứ i} 1.( Khởi tạo biến) K[0]:= -; 2.( Sắp xếp) for i:=2 to n do begin x=K[i]; j= i-1 ( j là số khoá đã được sắp xếp trước khoá k[i]) while x < K[j] do K[j +1] := K[j] j:=j -1; end; K[ j+1] :=x; End; 3.Return; c. Mô tả hoạt động của giải thuật sắp xếp theo kiểu chèn:               Ví dụ 1-1 Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ11.             Khoá Bước a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban đầu 5 6 2 2 10 12 9 10 9 3 Bước 1 5 6 Bước 2 2 5 6 Bước 3 2 2 5 6 Bước 4 2 2 5 6 10 Bước 5 2 2 5 6 10 12 Bước 6 2 2 5 6 9 10 12 Bước 7 2 2 5 6 9 10 10 12 Bước 8 2 2 5 6 9 9 10 10 12 Bước 9 2 2 3 5 6 9 9 10 10 12 Hình 2-2: Sắp xếp xen bảng mô tả sắp xếp kiểu chèn (Insert_sort) Ví dụ Cho dãy số a:                12 2 8 5 1 6 4 15 Dừng II. Sắp xếp theo kiểu nổi bọt (bubble_sort) 1. Lý thuyết liên quan đến giải thuật sắp xếp: - Sử dụng cấu trúc mảng 2. Ý Tưởng giải thuật: Dãy khoá cần sắp xếp được duyệt từ dưới lên,nếu trên đường đi gặp hai khoá kế cận ngược chiều sắp xếp thì đổi chỗ va quá trình lặp lại. Như vậy sau lượt thứ nhất khoá nhỏ nhất được xắp ở vị trí nhỏ nhất, lượt thứ hai được sắp xếp vào vị trí thứ 2 cứ như thế cho đến khi tất cả các khoá được sắp xếp. * Giải thuật: - Nội dung của phương pháp này là bước thứ i(i=1,2,3,…..,n-1) ta lựa chọn phần tử nhỏ nhất trong dãy từ a[1]…a[n] có thứ tự. - Giải thuật như sau: Procedure buble_sort(k,n) 1.(Khởi tạo) For i:=1 to n-1 do For j:=n down to i+1 do begin If k[j]<k[j-1] then begin X:=k[j]; k[j]:=k[j-1]; k[j-1]:=x; end; end; 2.Return * Mô tả hoạt động giải thuật sắp xếp nổi bọt  Ví dụ 1-2: Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ 1-1.             Khoá Bước a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban đầu 5 6 2 2 10 12 9 10 9 3 Bước 1 2 5 6 2 3 10 12 9 10 9 Bước 2 2 5 6 3 9 10 12 9 10 Bước 3 3 5 6 9 9 10 12 10 Bước 4 5 6 9 9 10 10 12 Bước 5 6 9 9 10 10 12 Bước 6 9 9 10 10 12 Bước 7 9 10 10 12 Bước 8 10 10 12 Bước 9 10 12 Kết quả 2 2 3 5 6 9 9 10 10 12 Bảng sắp xếp nổi bọt Ví dụ Cho dãy số a: 12 2 8 5 1 6 4 15 III. Sắp xếp kiểu lựa chọn( Selection sort). 1. Lý thuyết liên quan: * Cấu trúc dữ liệu; - Sử dụng cấu trúc mảng. 2. Giải thuật. a. Ý tưởng giải thuật. - Ở lượt thứ I của giải thuật, ta phải lấy ra phần tử đầu tương ứng đầu dãy và sau đó tìm min dãy còn lại Ki, Ki+1,…,Kn. Rồi so sánh min đó với phần tử đầu dãy. Nếu số min nhỏ hơn phần tử đầu dãy thì đổi chỗ. Sau jlựơt thì jkhoá nhỏ hơn sẽ được xếp vào vị trí thứ nhất, thứ hai, thứ jtương ứng. Thực hiện n-1 lần lượt b. Giải thuật. Nội dung của phương pháp này là ở bước thứ I (i= 1,2,..,n-1) ta lựa chọn phần tử nhơ nhất trong dãy a[i]..a[n] rồi đổi chỗ phần tử này với phần tử a[i]. Cuối cùng ta sẽ có dãy a[i]..a[n] có thứ tự. Procedure Select_sort(k,n) 1.Khởi tạo. for i:=1 to n-1 begin m:=I {m: chỉ số của phần tử min} for j:= i+1 to n do if K[j]<K[m] then m:=j; if K[m]<K[i] then begin X:=K[m] K[m]:=K[i]; K[i]:=X; End; End; 2.Return. c. Mô tả hoạt động của sắp xếp kiểu lựa chọn Hình 2-1: Sắp xếp chọn Ví dụ1-3: Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3            Khoá Bước a[1] a[2] a[3] a[4] A[5] a[6] A[7] a[8] a[9] a[10] Ban đầu 5 6 2 2 10 12 9 10 9 3 Bước 1 2 6 5 2 10 12 9 10 9 3 Bước 2 2 5 6 10 12 9 10 9 3 Bước 3 3 6 10 12 9 10 9 5 Bước 4 5 10 12 9 10 9 6 Bước 5 6 12 9 10 9 10 Bước 6 9 12 10 9 10 Bước 7 9 10 12 10 Bước 8 10 12 10 Bước 9 10 12 Kết quả 2 2 3 5 6 9 9 10 10 12 Bảng mô tả sắp xếp kiểu lựa chọn          Ví dụ Cho dãy số a:    12 2 8 5 1 6 4 15 IV. Sắp xếp kiểu vun đống ( heap sort) 1. Lý thuyết liên quan a. Cấu trúc dữ liệu - Sử dụng cấu trúc kiểu mảng. b. Giải thuật; * Ý tưởng giải thuật: Thực hiện sắp xếp đối với cây nhị phân hoàn chỉnh. Giải thuật gồm hai phần: + Giai đoạn I: Tạo đống ban đầu, gồm 2 bước: - Bước 1: Dựng cây nhị phân ban đầu, gồm 2 bước khoá ban đầu ( gốc của cây là khoá đầu dãy ), thực hiện từ trên xuống dưới, từ trái sang phải, hết mức này sang mức khác. Cây nhị phân được lưu trữ kế tiếp trong máy ( nếu như nút cha có chỉ sô là I thì 2 con có chỉ số là 2i, 2i+1 Ngược lại: nếu như mức con có chỉ số là jthì nút cha có chỉ số [j/2] - Bước 2: Tạo đống ban đầu (đống: là cây nhị phân hoàn chỉnh mà khoá nut cha > khoá nút con. Sau khi tạo đống ban đầu, khoá lớn nhất nằm ở gốc của cây. + Giai đoạn 2: Thực hiện sắp xếp có nhiều lựơt được thực hiện, mỗi lượt gồm 2 bước. - Bước 1: Đưa khoá trội về đúng vị trí sắp xếp bằng cách đổi chỗ cho khoá trội cho khoá đang ở vị trí đó ( từ dưới lên và từ phải sang trái, mức này sang mức khác) - Bước 2: Vun lại thành đống đối với cây nhị phân sau khi đã loại khoá trội ra khỏi đống ( chọn con lớn nhất trong 2 con để đưa lên). Quá trình đươc lặp lại cho đến khi cây rỗng ( tất cả các khoá được sắp xếp ). C. Giải thuật. { Việc thực hiện vun đống được thực hiện lặp đi lặp lại nhiều lần nên ta sẽ xây dựng 1 thủ tục để thực hiện vun đống, với cây có gốc là I và có n nút }. Procedure Vundong (i,n) {Giải thuật nhăm vun đống đối với cây nhị phân hoàn chỉnh có gốc là I mà 2 cây con có gốc tương ứng 2i, 2i+1, đã là đống. 1{khởi tạo}. { Khoá cha: là biến lưu trữ nút cha} Khoacha=K[i] jchỉ số của các con. Khoacha:=K[i]; j:=2i; while j,<n do begin {Tìm con lớn nhất trong 2 con }. If j<n and K[j] <K[j+1] then j: =j+1; {So sánh khoá cha lớn hơn con lớn nhất} If Khoacha[j/2]=Khoacha; {Đưa khoá cha vào đúng vị trí} return; end; 3. { Khoá con lớn nhất > Khoacha} K[]= K[j] ; j:= 2j {Chuyển khoá con lớn nhất lên và đi xuống} end; K[]= Khoacha; End; 3. Return. Giải thuật Heap_sort. Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này. Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp. Giả sử dữ liệu cần sắp xếp là dãy số : 5 2 6 4 8 1được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau : Trong đó 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+1, do đó phầ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. Trong ví dụ trên ta có : Loạ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 : Có thể nhận thấy toàn bộ nhánh trái của gốc 8 cũ được bảo toàn, do vậy bước kế tiếp để chọn được phần tử lớn nhất hiện hành là 6, chỉ cần làm thêm một phép so sánh 1 với 6. Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là -?, khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp. Trên đây là ý tưởng của giải thuật sắp xếp cây. Procedure Heap_sort (k,n) 1{khởi tạo đống ban đầu}; for i:= n div2 downto 1 do call Vundong ( 1,n); 2{Sẵp xếp}. for i:= n-1 downto 1 do begin {Sắp xếp} x:= K[1]; K[1]:= K[i+1]; K[i+1]:= x; { Thực hiện vun đống n-1}. Vundong(1,i) ; End; d. Mô tả hoạt động minh họa kiểu sắp xếp trên. V. Sắp xếp theo kiểu Quick_sort. 1. Lý thuyết liên quan. a. Cấu trúc dữ liệu - Sử dụng cấu trúc kiểu mảng; b.Giải thuật: * Ý tưởng giải thuật: - Ban đầu chọn khoá ngẫu nhiên làm khoá “ chốt”, sau lượt sắp xếp thì bảng khoá sẽ được chia thành 2 bảng con: Bảng khoá trước chốt: chứa khoá nhỏ hơn chốt. Bảng khóa sau khi chốt chứa các khoá lớn hơn khoá chốt. Muốn vậy các khoá trong dãy (ki, kj) phải được so sánh với khoá chốt để đổi chỗ cho nhau, đổi chỗ cho chốt. Nếu nhỏ hơn chốt và nằm trước chốt. Khi việc đổi chỗ được hoàn thành thị khoá chốt sẽ được xếp đúng vị trí thực và bảng khoá được chia thành 2 bảng khoá con. Với mỗi bảng khoá con này 1 kỹ thuật tương tự áp dụng cho đến khi tất cả các khoá được sắp xếp - 1,Chọn khoá đầu dãy l: khoá chốt, để phát hiện 2 khoá cần phải đổi chỗ cho nhau hoặc cho chốt ta sử dụng 2 chỉ số I,jthì K[i]; K[j] Ban đầu: i:=2; jn Khoá Ki > chot thì j:=j-1 cho đến khi +, Nếu Ki < chot; i:=i+1; +, Nếu Ki > chot; Kj được sử dụng khoachot Nếu Kj > chot thì j:=j-1 Cho đến khi Kj <chot thì ta dừng. Thực hiện so sánh chỉ số i và j. Nếu như i <jthì Ki đổi chỗ Kj và quá trình được lặp lại với Jcố định và i tăng; Nếu như i >= jthì khóa chốt được đưa vào đúng vị trí bằng đổi chỗ khoá cho chốt cho K[j]. Đến đây ta kết thúc 1 lượt sắp xếp và tăng quá trình lặp lại với mỗi bảng khóa con cho đến khi tất cả khoá được sắp xếp. * Giải thuật Procedure Quick sort ( d, csduoi, cstren ); + Ta sử dụng 1 khoá phụ có giá trị lớn hơn tất cả các khoá trong dãy thực và đặt ở cuối dãy, K[n+1] < K[i] ( i= 1,..,n ).Thêm biến khoachot để lưu trữ khoá chốt đang xét hiện thời. Sử dụng 2 chỉ số i, jphát hiện hai khoá ki, kj cần phải đổi chỗ 2 biến csduoi, cstren để xác định 2 biên của bảng khoá đang xét, biến lg = false để đánh dấu bảng khoá được phân làm 2 bảng khoá con chỉ số i ban đầu i:=1; j:= n = cstren} Procedure Quick_sort (k, csduoi, cstren); 1{khởi tạo}. lg:= true; 2{Thực hiện sắp xếp}. if csduoi <= cstren then begin i:= csduoi; j:= cstren+1; khoachot= k[ csduoi]; end; while lg do i:= i+1; j:= j-1; while k[j] > khoachot do j:= j-1; if i< tư bản chủ nghĩa then k[i] k[j]; else lg:= false; end; {Đưa khoachot vào đúng vị trí } khoachot k[j]; call Quick_sort ( k, csduoi, j-1); ( sắp xếp bảng trước chốt); call Quick_ sort ( k, i+1, cstren); ( sắp xếp bảng sau chốt); 3. Return. D, Mô tả hoạt động của giải thuật sắp xếp kiểu Quick_sort. * V í dụ Cho dãy số a: 12 2 8 5 1 6 4 15 Phân hoạch đoạn l =1,r=8: x = A[4] =5 Phân hoạch đoạn l =1, r = 3: x = A[2] = 2 Phân hoạch đoạn l = 5, r = 8: x = A[6] = 6 Phân hoạch đoạn l = 7, r = 8: x = A[7] = 6 Dừng. Ðánh giá giải thuật Hiệu qủa thực hiện của giải thuật QuickSort phụ thuộc vào việc chọn giá trị mốc. Trường hợp tốt nhất xảy ra nếu mỗi lần phân hoạch đều chọn được phần tử median (phần tử lớn hơn (hay bằng) nửa số phần tử, và nhỏ hơn (hay bằng) nửa số phần tử còn lại) làm mốc, khi đó dãy được phân chia thành 2 phần bằng nhau và cần log2(n) lần phân hoạch thì sắp xếp xong. Nhưng nếu mỗi lần phân hoạch lại chọn nhằm phần tử có giá trị cực đại (hay cực tiểu) là mốc, dãy sẽ bị phân chia thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại gồm (n-1) phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong. Ta có bảng tổng kết Trường hợp Ðộ phức tạp Tốt nhất n*log(n) Trung bình n*log(n) Xấu nhất n2 VI. Sắp xếp kiểu hoà nhập hai đường ( giả sử dãy khoá cần sắp xếp là dãy số); 1. Lý thuyết có liên quan: a. Cấu trúc dữ liệu: - Sử dụng cấu trúc mảng; b. Ý tưởng giải thuật; + Cho phép hợp nhất các khoá của 2 bảng khoá đã được sắp xếp thành một bảng khoá cũng được sắp xếp có kích thước lớn hơn. + Nguyên tắc thực hiện như sau: Ở mỗi lượt ta chọn khoá nhỏ hơn trong 2 khoá nhỏ nhất của 2 bảng lương ứng để đưa ra miện sắp xếp, và quá trình lặp lại cho đến khi 1 trong 2 bảng đã hết, lúc đó ta chỉ việc đưa phần còn lại của bảng kia ra miền sắp xếp. * Giải thuật: Giải thuật nhằm thực hiện một lượt hoà nhập 2 mạch với độ dài l ( có thể một trong 2 mạch có độ dài nhỏ hơn l ) để cho một mạch lớn hơn. K là dãy khoá đã cho, có n phần tử K[1], K[2],..,K[n]. Các dãy con trong K đã là các mạch có độ dài bằng l, trừ dãy con cuối cùng có thể có độ dài bé hơn l. Q: là số cặp mạch có độ dài l thì Q=; Gọi S:=2*l*Q thì S là số các phần tử của Q của mạch. R= n-S là số các phần tử còn lại của dãy K. Procedure MPass (k,n,l,x); [X: là vecto có n phần tử được dung để lần lượt chứa các phần tử của K sau khi hoà nhập] 1.Q:= ndiv(2*l); S:= 2*l*Q; R:= n-S; 2{hoà nhập từng cặp mạch}. For i:=1 to Q do begin LB:= 1+ (2*j-2)*l; { Xác định biên dưới của mạch thứ nhất} call MERGE ( k, l, LB, k, l, LB+1,x, LB); end; 3. ( chỉ còn một mạch); if R<= 1 then for j:=1 to R do x[s+j] := A[s+j]; 4.( còn 2 mạch nhưng một mạch có độ dài nhỏ hơn 1). Else Call MERGE (k, l, s+1, k, R-1, l+s+1, x, S+l); 5. Return. thủ tục MPASS này sẽ được gọi tới trong thủ tục thực hiện sắp xếp kiểu hoà nhập hai đường trực tiếp. Procedure Straight_Msort (k,n); 1.( Khởi tạo số phần tử trong mạch) l:=1; 2. while l<n begin call MPASS (k,n,l,x); ( Thực hiện hoà nhập và chuyển các phần tử vào x); 3. call MPASS ( x,n,2*l,k); (thực hiện hoà nhập và chuyển các phần tử vào k) 4. l:=4*l; end; 5.Return; Diễn giải phần chương trình chạy. I - Phần chương trình chính: BEGIN Init; Input; Readln; END. 1. Phần Input: Là một chương trình con có tác dụng: - Nhập dữ liệu. + Bắt đầu nhập dữ liệu (b) + Nhập số lượng các phần tử (n) + Các phần tử ( dayso[i] ) - Chọn lựa các cách sắp xếp: 1. Selection Sort - Sắp xếp kiểu lựa chọn 2. Insertion Sort - Sắp xếp kiểu chèn 3. Bubble Sort - Sắp xếp kiẻu nổi bọt 4. Quick Sort - Sắp xếp nhanh 5. Merge Sort - Sắp xếp kiểu hoà nhập 6. Heap sort - Sắp xếp kiểu đống - Cách thức sắp xếp: t ă ng dần (Ascending) hoặc giảm dần (Dicending). 2. Phần Output: Là một chương trình con có tác dụng: Xuất dữ liệu ra màn hình: - Dãy đã nhập chưa được sắp xếp - Dãy đã được sắp xếp theo yêu cầu. 3. Phần Init: Là một chương trình con có tác dụng: Tạo giao diện màn hình và bảng chọn từ bàn phím cho người sử dụng. 4. Phần các Proceduce giải thuật: Bao gồm các Procedure dùng để thực hiện các giải thuật sắp xếp khác nhau: 1. Procedure Selection Sort Giải thuật sắp xếp kiểu chọn lựa 2. Procedure Insertion_Sort Giải thuật sắp xếp kiểu chèn 3. Procedure Bubble_Sort Giải thuật sắp xếp kiểu nổi bọt 4. Procedure Quick_Sort Giải thuật sắp xếp nhanh 5. Procedure Merge_Sort 6. Procedure MPASS 7. Procedure STRAIGHT_MERGE_SORT Giải thuật sắp xếp kiểu Trộn lẫn 8. Procedure PushDown 9. Procedure Heap_sort Giải thuật sắp xếp kiểu vun đống Phần mã nguồn (Source Code) của chương trình được viết bằng ngôn ngữ lập trình pascal. Yêu cầu cấu hình hệ thống: - Máy PC sử dụng CPU Intel Pentium II, Celeron 100MHz hoặc cao hơn. - Hệ điều hành Windows 95, 98, ME, 2k, XP, Sever 2003. - Turbo Pascal 7.0 hoặc Free Pascal 2.0 có hỗ trợ đầy đủ thư viện. {Source code: } Program Thuat_toan_sap_xep; Uses Crt; Var dayso, daysotam, dayZ:Array[0..99] of Integer; F:Text; Tongphantu: Integer; {-------------------------------Begin Init---------------------------------} Procedure Init; Var i:Integer; Begin TextBackGround(LightGray); ClrScr; TextColor(Blue); For i := 2 to 79 do Begin Gotoxy(i,1); Write(chr(205)); Gotoxy(i,49); Write(chr(205)); Gotoxy(i,8); Write(Chr(205)); End; For i := 2 to 48 do Begin Gotoxy(1, i); Write(Chr(186)); Gotoxy(80, i); Write(Chr(186)); End; Gotoxy(1,1); Write(Chr(201)); Gotoxy(80,1); Write(Chr(187)); Gotoxy(1,8); Write(Chr(204)); Gotoxy(80,8); Write(Chr(185)); Gotoxy(1,49); Write(Chr(200)); Gotoxy(80,49); Write(Chr(188)); Gotoxy(20,8); Write(Chr(209)); Gotoxy(20,49); Write(Chr(207)); For i := 9 to 48 do Begin Gotoxy(20,i); Write(chr(179)); End; Gotoxy(25,2); Write('SORTING ALGORITHMS DEMO PROGRAM'); Gotoxy(8,4); TextColor(Red); Write('Infomation Technology Department - National economic University'); Gotoxy(30,6); TextColor(Blue); Write('Developer: Six Group'); Gotoxy(5, 10); Write('Algorithms:'); For i := 2 to 19 do Begin Gotoxy(i, 12); Write(Chr(196)); ENd; TextColor(Red); Gotoxy(3, 14); Write('1. SELECTION SORT'); Gotoxy(3, 16); Write('2. INSERTION SORT'); Gotoxy(3, 18); Write('3. BUBBLE SORT'); Gotoxy(3, 20); Write('4. QUICK SORT'); Gotoxy(3, 22); Write('5. MERGE SORT'); Gotoxy(3, 24); Write('6. HEAP SORT'); End; {---------------------------End of Init------------------------------------} {---------------------------Begin of OutPut--------------------------------} Procedure OutPut(var max:Integer; blnMergeSort: boolean); Var i, j:Integer; Begin For i := 10 to 48 do Begin For j := 24 to 79 do Begin Gotoxy(j,i); Write(' '); End; End; Gotoxy(24, 10); Write('- Day truoc khi sap xep: '); Gotoxy(24,12); TextColor(Red); For i := 1 to max do Begin Write(daysotam[i], ' '); End; TextColor(Blue); Gotoxy(24, 15); Write('- Day sau khi sap xep: '); TextColor(Red); Gotoxy(24,17); If not blnMergeSort then For i := 1 to max do Begin Write(dayso[i], ' '); End else For i := 1 to max do Begin Write(dayZ[i], ' '); End; End; {----------------------------------End of Output--------------------------} {----------------------------------Begin of SELECTION_SORT----------------} Procedure SELECTION_SORT(Var K:Array of Integer; numElement:Integer; direction:Integer); Var i,j,m, X:Integer; Begin If direction = 1 then Begin For i := 1 to numElement - 1 do Begin m := i; For j := i + 1 to numElement do If K[j] < K[m] then m := j; If (m i) Then Begin X := K[i]; K[i] := K[m]; K[m] := X; End; End; End; If direction = 0 then Begin For i := 1 to numElement - 1 do Begin m := i; For j := i + 1 to numElement do If K[j] > K[m] then m := j; If (m i) Then Begin X := K[i]; K[i] := K[m]; K[m] := X; End; End; End; End; {-----------------------------End of SELECTION_SORT------------------------} {-----------------------------Begin of INSERTION_SORT----------------------} Procedure INSERTION_SORT(Var K:Array of Integer; noe: Integer; dir:Integer); Var i, j, X: Integer; Begin K[0] := -32500; If dir = 1 then Begin For i := 2 to noe do Begin X := K[i]; j := i - 1; While X < K[j] do Begin K[j+1] := K[j]; j := j - 1; End; K[j+1] := X; End; End; If dir = 0 then Begin For i := 2 to noe do Begin X := K[i]; j := i - 1; While X > K[j] do Begin K[j+1] := K[j]; j := j - 1; End; K[j+1] := X; End; End; End; {-------------------------End of INSERTION_SORT----------------------------} {-------------------------Begin of BUBBLE_SORT-----------------------------} Procedure BUBBLE_SORT(Var K:Array of Integer; numOfEle: Integer; dir:Integer); Var i, j, X: Integer; Begin If dir = 1 then For i := 1 to numOfEle do For j := numOfEle downto i + 1 do If K[j] < K[j-1] Then Begin X := K[j]; K[j] := K[j-1]; K[j-1] := X; End; If dir = 0 then For i := 1 to numOfEle do For j := numOfEle downto i + 1 do If K[j] > K[j-1] Then Begin X := K[j]; K[j] := K[j-1]; K[j-1] := X; End; Output(numOfEle, false); End; {------------------------End of BUBBLE_SORT--------------------------------} {------------------------Begin of QUICK_SORT-------------------------------} Procedure QUICK_SORT(Var K:Array of Integer; lowerBound: Integer; upperBound: Integer); Var i, j, KEY, X, Y:Integer; B: boolean; Begin B := true; If (lowerBound < upperBound) Then Begin i := lowerBound; j := upperBound + 1; KEY := K[lowerBound]; While B Do Begin i := i + 1; While K[i] < KEY Do i := i + 1; j := j - 1; While K[j] > KEY Do j := j - 1; If i < j then Begin X := K[i]; K[i] := K[j]; K[j] := X; End Else B := false; End; Y := K[lowerBound]; K[lowerBound] := K[j]; K[j] := Y; QUICK_SORT(K, lowerBound,j - 1); QUICK_SORT(K, j + 1, upperBound); End; End; {------------------------End of QUICK_SORT---------------------------------} {------------------------Begin MERGE_SORT----------------------------------} Procedure MERGE_SORT(Var X:Array of Integer; b: Integer; m: Integer; n: Integer; Var Z:Array of Integer); Var i, j, k, s: Integer; Begin i := b; k := b; j := m + 1; While (i <= m) and (j <= n) Do Begin If X[i] <= X[j] Then Begin Z[k] := X[i]; i := i + 1; End Else Begin Z[k] := X[j]; j := j + 1; End; k := k + 1; End; If i > m then Begin For s := j to n do Begin Z[k] := X[s]; k := k + 1; End; End Else Begin For s := i to m do Begin Z[k] := X[s]; k := k + 1; End; End; End; {--------------------------End of MERGE_SORT-------------------------------} {--------------------------Begin of MPASS----------------------------------} Procedure MPASS(Var X:Array of Integer; Var Y:Array of Integer; n: Integer; l: Integer); Var i, s:Integer; Begin i := 1; While (i <= n - 2*l - 1) do Begin MERGE_SORT(X, i, i + l - 1, i + 2*l - 1, Y); i := i + 2*l; End; If (i + l - 1 < n) Then MERGE_SORT(X, i, i + l - 1, n, Y) Else Begin For s := i to n do Begin Y[s] := X[s]; End; End; End; {--------------------------End of MPASS------------------------------------} {--------------------------Begin of STRAIGHT_MERGE_SORT--------------------} Procedure STRAIGHT_MERGE_SORT(Var X:Array of Integer; n:Integer); Var l: Integer; Y: Array[0..99] of Integer; Begin l := 1; While l < n do Begin MPASS(X, Y, n, l); l := l + 1; MPASS(Y, X, n, l); l := l + 1; End; End; {--------------------------End of STRAIGHT_MERGE_SORT----------------------} {--------------------------Begin of Push down--------------------} {procedure PushDown (var first:integer; last:integer; K: array of integer); var r:integer; begin r:= first; while r <= last div 2 do if last = 2*r then begin if K[r] > K[last] then K[r] := K[last]; r:=last; end else if (K[r] > K[r*2]) and (K[2*r] <= K[2*r+1]) then begin K[r] := K[2*r]; r := 2*r ; end else if (K[r] > K[2*r+1]) and (K[2*r+1] < K[2*r]) then begin K[r] := K[2*r+1]; r := 2*r+1 ; end else r := last; end;} {--------------------------End of push down--------------------} {--------------------------Begin of HEAP_SORT--------------------} Procedure HeapSort(Var K:Array of Integer; so_pt: Integer; dir:Integer); var first:integer; begin for first := (so_pt div 2) downto 1 do PushDown (first,so_pt,K); for i := so_pt downto 2 do begin a[1] := a[i]; pushdown(1,so_pt-1,K); end; end; {--------------------------Begin Input-------------------------------------} Procedure Input; Var n:char; num: Integer; i: Integer; a: Integer; o: Integer; Begin Gotoxy(24, 10); TextColor(Blue); Write('- Bat dau nhap du lieu (b)'); Readln(n); If (n='B') or (n='b') then Begin Gotoxy(24, 12); Write('- So phan tu cua day N='); Readln(num); For i := 1 to num do Begin Gotoxy(24, 12+2*i); Write(' + So thu ', i, ' = '); Readln(dayso[i]); End; For i := 1 to num do Begin daysotam[i] := dayso[i]; End; Gotoxy(24, 14+2*num); Write('Sap xep xuoi (1) hay nguoc (0)?'); Readln(o); Gotoxy(24, 16+2*num); Write('Chon thuat toan (1/2/3/4/5): '); Readln(a); End; case a of 1: Begin SELECTION_SORT(dayso, num, o); Output(num, false); End; 2: Begin INSERTION_SORT(dayso, num, o); Output(num, false); End; 3: Begin BUBBLE_SORT(dayso, num, o); Output(num, false); End; 4: Begin QUICK_SORT(dayso, 1, num); Output(num, false); End; 5: Begin STRAIGHT_MERGE_SORT(dayso, num); OutPut(num, false); End; 6: Begin PUSHDOWN (1 , num, dayso); HEAP_SORT(dayso, num); output (num, false); end; End; {-----------------------------End of Input---------------------------------} {-----------------------------Main Program---------------------------------} BEGIN Init; Input; Readln; END. Các tài liệu tham khảo - Giáo trình cấu trúc dữ liệu và giải thuật PGS.TS Hàn Viết Thuận - NXB Thống kê - Cấu trúc dữ liệu và giải thuật GS Đỗ Xuân Lôi – NXB ĐHQG Hà Nội - Các giáo trình điện tử về Cấu trúc dữ liệu và giải thuật khác MỤC LỤC Lời mở đầu Giới thiệu và phân tích bài toán. I. Sắp xếp kiểu chèn ( thêm dần ) – insertion sort II. Sắp xếp theo kiểu nổi bọt (bubble_sort) III. Sắp xếp kiểu lựa chọn( Selection sort). IV. Sắp xếp kiểu vun đống ( heap sort) V. Sắp xếp theo kiểu Quick_sort. VI. Sắp xếp kiểu hoà nhập hai đường ( giả sử dãy khoá cần sắp xếp là dãy số) Diễn giải phần chương trình chạy. ._.