Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
Giải thuật sắp xếp dữ liệu
Lời mở đầu
Trong kỷ nguyên Công Nghệ Thông Tin, cấu trúc dữ liệu là nền tảng trong
mọi hoạt động của các tổ chức.Cấu trúc dữ liệu được biểu hiện dưới nhiều khía
cạnh. Cấu trúc dữ liệu và giải thuật là một môn học cơ sở trong chương trình
đào tạo trang bị cho sinh viên những kiến thức cơ bản về cấu trúc, dữ liệu khi
thiết kế và cài đặt các phần mềm.
Trong các bước giải quyết một bài toán trên máy tính, công đoạn lập trình
có vai trò quan trọng nhất. Việc ứng dụng 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.
Sắp xếp dữ liệu - giải thuật và ứng dụng
1
Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
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.
Sắp xếp dữ liệu - giải thuật và ứng dụng
2
Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuậ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]
Sắp xếp dữ liệu - giải thuật và ứng dụng
3
Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
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á
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
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
Bước
9
3
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
Sắp xếp dữ liệu - giải thuật và ứng dụng
2 8
5
1
6
4
15
4
Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
Dừng
Sắp xếp dữ liệu - giải thuật và ứng dụng
5
Website: http://www.docs.vn Email :
[email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
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]
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}
Sắp xếp dữ liệu - giải thuật và ứng dụng
14
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
Khoacha=K[i]
jchỉ số của các con.
Khoacha:=K[i];
j:=2i;
while j, Khoacha}
K[ j / 2 ]= K[j] ;
j:= 2j
{Chuyển khoá con lớn nhất lên và đi xuống}
end;
K[ j / 2 ]= 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
Sắp xếp dữ liệu - giải thuật và ứng dụng
15
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
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 :
Sắp xếp dữ liệu - giải thuật và ứng dụng
16
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
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:
Sắp xếp dữ liệu - giải thuật và ứng dụng
17
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & 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 = 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,
Sắp xếp dữ liệu - giải thuật và ứng dụng
18
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuậ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
Sắp xếp dữ liệu - giải thuật và ứng dụng
19
Website: http://www.docs.vn Email : [email protected] Tel (: 0918.775.368
Cấu trúc dữ liệu & giải thuật
Sắp xếp dữ liệu - giải thuật và ứng dụng
20