Download miễn phí Đề tài Giải thuật sắp xếp dữ liệu



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.
 
 


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-17-de_tai_giai_thuat_sap_xep_du_lieu.UWyT9oJ8rx.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54965/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

đã 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 tui đã đư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
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; j= i-1 ( j là số khoá đã được sắp xếp trước khoá k)
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..a[n] rồi đổi chỗ phần tử này với phần tử a. Cuối cùng ta sẽ có dãy a..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 then begin
X:=K[m]
K[m]:=K;
K:=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 để t...

---

Yêu cầu Download