intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST
Báo xấu
67
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phương pháp chọn, phương pháp chèn, phương pháp chèn nhị phân, phương pháp nổi bọt, phương pháp sắp xếp nhanh, phương pháp vun đống là những nội dung chính trong "Bài giảng Cấu trúc dữ liệu - Chương 5: Sắp xếp". Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - Chương 5: Sắp xếp

  1. CHƯƠNG 5 SẮP XẾP 1
  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   2
  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 ti ̣ ́nh, đượ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 ̣ ̀ 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. 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. 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
  6. 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
  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].   7
  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]=­∞.   8
  9. 5.2 Phương pháp chèn void SX_chen(int *k, int n) {int j; for(int i=2;i
  10. 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
  11. 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]
  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; }   12
  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(n2)   13
  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.   14
  15. 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
  16. 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
  17. 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
  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(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
  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.   19
  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. ­ Vun lại thành đống cho cây chứa những  nút còn lại.    20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
4=>1