Cấu trúc dữ liệu và giải thuật - Chương 5: Sắp xếp

CHƯƠNG 5SẮP XẾP1Chương 5: Sắp xếp5.1 Phương pháp chọn5.2 Phương pháp chèn5.3 Phương pháp chèn nhị phân5.4 Phương pháp nổi bọt5.5 Phương pháp sắp xếp nhanh5.6 Phương pháp vun đống24.1 bài toán sắp xếpCó 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.34.1 bài toán sắp xếpSắ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ự.45.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. 55.1 Phương pháp chọnThuậ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=1;i--) adjust(k,i,n);for(i=n-1;i>=1;i--) {swap(&k[i+1],&k[1]); adjust(k,1,i); }return;}265.5 Phương pháp vun đốngvoid adjust(int *k,int i, int n){int key=k[i],j=2*i;//chọn con ứng với khóa lớn nhất trong 2 con của iwhile(jk[j]) {k[floor(j/2)]=key;return;}//chuyển k lên trên và đi xuống k[floor(j/2)]=k[j];j=2*j; }k[floor(j/2)]=key;}275.5 Phương pháp vun đốngĐánh giá:- Độ phức tạp của thuật toán là O(nlog2n)28Bài tậpBài 1.Cho dãy khóa: 50,8,34,6,98,17,83,25,66,42,21,59,62,71,85,76. Viết chương trình sắp xếp dãy khóa trên theo thứ tự tăng dần, giảm dần bằng phương pháp:Sắp xếp chọnSắp xếp chènSắp xếp nổi bọtBài 2: Làm các bài tập chương 6, trang 143-146 sách Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi, NXB Đại học Quốc gia Hà Nội.29