Kiến Thức Chung

Tiểu luận giải thuật sắp xếp dữ liệu

Tiểu luận giải thuật sắp xếp dữ liệu

doc – 38 trang

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ở màn

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 dấu hiệu 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 nền tảng trong chương trình

huấn luyện trang bị cho sinh viên những tri thức cơ bản về cấu trúc, dữ liệu khi

thiết kế và thiết lập các software.

Trong các bước khắc phục một bài toán trên PC, giai đoạn lập trình

có vai trò trọng yếu 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 phong phú. Điều đó đòi hỏi phải thiết kế các giải thuật

khắc phục một cách tốt nhất vấn đề đặt ra.

Sắp xếp (sort) là một quá trình thay đổ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 nào đó. Sắp xếp đóng một vai trò

rất trọng yếu trong việc tìm kiếm dữ liệu. Ví dụ, tất cả 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 ngành nghề kinh

tế việc sắp lại càng trọng yếu.

Với sự bùng phát 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 số đó, ngôn ngữ lập trình cấp cao

pascal là một ngôn ngữ có định kiểu mạnh mẽ, thân thiện với ngôn ngữ tự nhiên

và được nhiều người biết tới. Đó chính là nguyên nhân 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.

Để khắc phục 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 đã mang 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

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 thiết lập 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 tìm hiểu các giải thuật sắp xếp, thiết lập

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 thích 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

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á trước nhất ta mang vào

dãy khoá sắp xếp một khoá giả có giá trị nhỏ hơn toàn bộ 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;

Sắp xếp dữ liệu – giải thuật và ứng dụng

Xem Thêm :   Tải Game Loan 12 Su Quan Online Tren Pc, Pubg Mobile (Kr) 1

Xem Thêm :  Mẫu giấy giới thiệu mới nhất 2021 tải file word

3

Cấu trúc dữ liệu & giải thuật

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

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

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ư vậy cho đến khi toàn bộ 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]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

Sắp xếp dữ liệu – giải thuật và ứng dụng

6

Cấu trúc dữ liệu & giải thuật

Ví dụ 1-2: Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ 1-1.

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

9

3

Bước 1

2

5

6

2

3

10

12

9

10

9

2

5

6

3

9

10

12

9

10

3

5

6

9

9

10

12

10

5

6

9

9

10

10

12

6

9

9

10

10

12

9

9

10

10

12

9

10

10

12

10

10

12

10

12

10

12

Bước

Bước 2

Bước 3

Bước 4

Bước 5

Bước 6

Bước 7

Bước 8

Bước 9

Kết quả

2

2

3

5

6

9

9

10

Bảng sắp xếp nổi bọt

Ví dụ

Cho dãy số a: 12

2

Sắp xếp dữ liệu – giải thuật và ứng dụng

8

5

1

6

4

15

7

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

8

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

9

Cấu trúc dữ liệu & giải thuật

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.

Sắp xếp dữ liệu – giải thuật và ứng dụng

10

Cấu trúc dữ liệu & giải thuật

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]if K[m]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á

a[1] a[2]

a[3]

a[4]

A[5]

a[6]

A[7]

a[8]

a[9] a[10]

Bước

Sắp xếp dữ liệu – giải thuật và ứng dụng

11

Cấu trúc dữ liệu & giải thuật

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

2

5

6

10

12

9

10

9

3

3

6

10

12

9

10

9

5

5

10

12

9

10

9

6

6

12

9

10

9

10

9

12

10

9

10

9

10

12

10

10

12

10

10

12

10

12

Bước 2

Bước 3

Bước 4

Bước 5

Bước 6

Bước 7

Bước 8

Bước 9

Kết quả

2

2

3

5

6

9

9

Bảng mô tả sắp xếp kiểu lựa chọn

10

Ví dụ

Cho dãy số a:

12

2

Sắp xếp dữ liệu – giải thuật và ứng dụng

8

5

1

6

4

15

12

Cấu trúc dữ liệu & giải thuật

Xem Thêm :   Phân phối chương trình Ngữ Văn 8 mới nhất

Xem Thêm :  Học lỏm cách luộc hột vịt lộn ngon nhất ăn hoài không ngán

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 so với cây nhị phân hoàn chỉnh.

Sắp xếp dữ liệu – giải thuật và ứng dụng

13

Cấu trúc dữ liệu & giải thuật

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ữ tiếp theo trong máy ( nếu

như nút cha có chỉ sô là I thì 2 con có chỉ số là 2i, 2i+1

Trái 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 khoảng thời gian 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: Mang 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 so với cây nhị phân sau thời điểm đã loại khoá

trội ra khỏi đống ( chọn con lớn nhất trong 2 con để mang lên).

Quá trình đươc lặp lại cho đến khi cây rỗng ( toàn bộ 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 so 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.

Sắp xếp dữ liệu – giải thuật và ứng dụng

14

Cấu trúc dữ liệu & giải thuật

Khoacha:=K[i];

j:=2i;

while j,{Tìm con lớn nhất trong 2 con }.

If jj: =j+1;

{So sánh khoá cha to hơn con lớn nhất}

If Khoacha[j/2]=Khoacha;

{Mang khoá cha vào đúng vị trí}

return; end;

3. { Khoá con lớn nhất > 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ì nguyên nhân 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 để khắc phục vấn đề vừa nêu là phải tìm thấy đượ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 sắp xếp

theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau :

Sắp xếp dữ liệu – giải thuật và ứng dụng

15

Cấu trúc dữ liệu & giải thuật

Trong số đó 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à mang phần tử lớn nhất về đúng

vị trí), thì việc update 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 tiếp theo 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 tiếp theo để 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.

Sắp xếp dữ liệu – giải thuật và ứng dụng

16

Cấu trúc dữ liệu & giải thuật

Xem Thêm :   Hibernate java là gì

Xem Thêm :  Tuổi rồng sinh năm bao nhiêu

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 toàn bộ

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 thời điểm chốt chứa các khoá to hơn khoá chốt.

Sắp xếp dữ liệu – giải thuật và ứng dụng

17

Cấu trúc dữ liệu & giải thuậ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 thiện 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ự ứng dụng cho đến khi toàn bộ 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 Nếu như i tăng;

Nếu như i >= jthì khóa chốt được mang 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 toàn bộ 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ị to hơn toàn bộ 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ận 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;

Sắp xếp dữ liệu – giải thuật và ứng dụng

18

Cấu trúc dữ liệu & giải thuật

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 ivàlt; tư bản chủ nghĩa then k[i]  k[j];

else lg:= false;

end;

{Mang 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

Cấu trúc dữ liệu & giải thuật

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ử to 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 tách 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 tách thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn

Sắp xếp dữ liệu – giải thuật và ứng dụng

20

Xem thêm bài viết thuộc chuyên mục: Giáo Dục

Xem thêm bài viết thuộc chuyên mục: Kiến Thức Chung

Related Articles

Back to top button