1
CHƯƠNG 5
SẮP XẾP

2
Chương 5: Sắp xếp
5.1 Phương pháp chọn
5.2 Phương pháp chèn
5.3 Phương pháp chèn nhị phân
5.4 Phương pháp nổi bọt
5.5 Phương pháp sắp xếp nhanh
5.6 Phương pháp vun đống

3
4.1 bài toán sắp xếp
Có một tập n đối tượng. Mỗi đối tượng có
nhiều thuộc tính, được thể hiện bằng một
kiểu bản ghi gồm nhiều trường. Sắp xếp là
quá trình bố trí lại các bản ghi theo một
trường gọi là khóa.
Ví dụ trong bảng danh bạ gồm các bản ghi
có tên cơ quan, địa chỉ, số điện thoại. Sổ
danh bạ thường được sắp xếp theo trường
khóa là tên cơ quan để dễ tìm kiếm.

4
4.1 bài toán sắp xếp
Sắp xếp là thao tác cần thiết hay gặp trong
quá trình lưu trữ và quản lý dữ liệu. Có 2
phương pháp sắp xếp: sắp xếp trong tác động

}
return;
}

7
5.2 Phương pháp chèn

Ý tưởng:
Dãy khóa cần xếp là k[1], k[2],…, k[n].
Đầu tiên khóa k[1] chỉ có một khóa đã được
sắp xếp. Xét thêm k[2],so sánh nó với k[1]
để xác định chỗ chèn nó vào và ta có 2 khóa
được sắp xếp. Đối với k[3] lại so sánh với
k[2], k[1] và cứ như vậy đến khi xét xong
k[n].

8
5.2 Phương pháp chèn

Cài đặt:
Để có chỗ cho khóa mới phải dịch chuyển các
khóa lùi lại sau và dùng X làm ô nhớ phụ
chứa khóa đang được xét. Để khóa mới dù ở
vị trí đầu tiên cũng được chèn vào giữa
khóa nhỏ và lớn hơn nó, ta thêm vào khóa
giả k[0]=-∞.

9
5.2 Phương pháp chèn
void SX_chen(int *k, int n)


12
5.3 Phương pháp nổi bọt
void swap(int *c,int *d)
{int a;
a=*c;
*c=*d;
*d=a;
return;
}

13
Đánh giá 3 phương pháp:
-
Độ phức tạp trung bình của thuật toán
chung cho cả 3 phương pháp là O(n
2
)

14
5.4 Phương pháp sắp xếp nhanh

Ý tưởng:
Chọn khóa đầu tiên của dãy làm chốt. Mọi
phần tử nhỏ hơn khóa chốt phải được
xếp vào đầu dãy. Mọi phần tử lớn hơn
khóa chốt phải được xếp vào cuối dãy.
Muốn vậy, các phần tử trong dãy sẽ
được so sánh với khóa chốt và sẽ đổi vị
trí cho nhau.

return;}

18
5.4 Phương pháp sắp xếp nhanh
Đánh giá:
-
Độ phức tạp trung bình của thuật toán là
O(nlog
2
n)
-
Khi kích thước phân đoạn đã nhỏ, ta dùng
phương pháp sắp xếp đơn giản tiện hơn.

19
5.5 Phương pháp vun đống

Cài đặt:
Trước hết phải tạo đống là tạo ra cây nhị
phân hoàn chỉnh mà khóa ở nút cha bao giờ
cũng lớn hơn khóa ở các nút con của nó.
Cây nhị phân này được lưu trữ kế tiếp
trong máy.

20
5.5 Phương pháp vun đống
Giai đoạn thứ 2 gồm:
- Đổi chỗ của vị trí cuối cùng với khóa ở gốc
của đống để đưa khóa lớn nhất về vị trí
đúng.

42
87
94
36
23 11
65
99
58 74
giai đoạn 2: - đổi chỗ về vị trí đúng

24
5.5 Phương pháp vun đống
42
87
94
36
23 11
65 58 74
giai đoạn 2: - vun đống mới với cây còn lại

25
5.5 Phương pháp vun đống
11
23
36
42
87 94
58
99
65 74