Chapter 5: Sắp xếp

Chia sẻ: Lelong Bao | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST

Báo xấu

54
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Có một tập n đối tượng. Mỗi đối tượng có nhiều thuộc tính, được thể hiện bằng một kiểu bả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 gọi là khó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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chapter 5: Sắp xếp

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 bai toan sắp xếp ̀ ́ Có môt tâp n đôi tượng. Môi đôi tượng ̣ ̣ ́ ̃ ́ có nhiêu thuôc tinh, được thể hiên băng môt ̀ ̣ ́ ̣ ̀ ̣ kiêu ban 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 goi là khoa. ̣ ́ 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 bai toan 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
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]. 7
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]=-∞. 8
5.2 Phương pháp chèn void SX_chen(int *k, int n) {int j; for(int i=2;i
5.3 Phương pháp nổi bọt Cài đặt: Bảng các khóa sẽ được duyệt từ đáy lên đỉnh. Dọc đường nếu gặp 2 khóa kế cận ngược thứ tự ta sẽ đổi chỗ chúng với nhau. Sau mỗi lượt sắp xếp các giá trị khóa nhỏ sẽ nổi dần lên giống như bọt nước trong nồi nước đang sôi. 10
5.3 Phương pháp nổi bọt void SX_noibot(int *k, int n) {for(int i=1;i=i+1;j--) if(k[j]
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; } 12
Đá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(n2) 13
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. 14
5.4 Phương pháp sắp xếp nhanh Khi việc đổi chỗ đã thực hiện xong, dãy khóa được phân làm 2 đoạn. Đoạn đầu gồm các khóa nhỏ hơn chốt, đoạn sau gồm các khóa lớn hơn chốt, khóa chốt nằm giữa 2 đoạn. Hai đoạn sẽ được xử lý riêng giống như vậy. Quá trình xử lý từng đoạn sẽ kết thúc khi chỉ còn 1 phần tử. 15
5.4 Phương pháp sắp xếp nhanh void SX_nhanh(int *k, int L, int U) {int B=1; if(L
5.4 Phương pháp sắp xếp nhanh swap(&k[L],&k[j]); SX_nhanh(k,L,j-1); SX_nhanh(k,j+1,U); } return;} 17
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(nlog2n) - 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. 18
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. 19
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. - Vun lại thành đống cho cây chứa những nút còn lại. 20