CHƯƠNG 5
SẮP XẾP
1
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
2
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.
3
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
lên các bản ghi lưu trữ ở bộ nhớ trong và Sắp
xếp ngoài liên quan đến tập lớn các bản ghi
lưu trữ trên tệp. Chương này chỉ xét bài toán
sắp xếp trong theo thứ tự tăng của khóa. Sắp
xếp theo thứ tự giảm được làm hoàn toàn
tương tự.
4
5.1 Phương pháp chọn
Ý tưởng:
Dãy khóa cần sắp xếp là k[1],k[2],…, k[n]. Ở
lượt thứ i (i=1,2,3,…,n-2) ta sẽ chọn trong
dãy khóa k[i+1],…., k[n] khóa nhỏ nhất và
đổi chỗ nó với k[i]
Sau n-1 lượt khóa từ nhỏ đến lớn sẽ được sắp
xếp ở các vị trí thứ 1, thứ 2,…thứ n-1, thứ
n.
5
5.1 Phương pháp chọn
Thuật toán:
void SX_chon(int *k, int n)
{int i,x;
for(i=1;i=i+1;j--)
if(k[j]key) j--;
if(i- Xem thêm -