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

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ư 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
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á
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
Sắp xếp dữ liệu - giải thuật và ứng dụng
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]<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]
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
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
Sắp xếp dữ liệu - giải thuật và ứng dụng
12
Cấu trúc dữ liệu & giải thuật
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.
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ữ 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.
Sắp xếp dữ liệu - giải thuật và ứng dụng
14

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