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 và giải thuật: Chương 6 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Chia sẻ: Cxzvscv Cxzvscv | Ngày: | Loại File: PDF | Số trang:78

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

Chương 6 Sắp xếp nằm trong bài giảng cấu trúc dữ liệu và giải thuật nhằm trình bày về các nội dung chính: các phương pháp sắp xếp cơ bản, đánh giá các phương pháp, Quick - Sort và Heap_Sort, trình bày các thuật toán thông dụng cho việc sắp xếp trong (sắp xếp trên bộ nhớ trong - RAM).

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 và giải thuật: Chương 6 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

  1. Chương 6: Sắp xếp Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
  2. Nội dung  Các phương pháp sắp xếp cơ bản  Đánh giá các phương pháp  Quick_Sort  Heap_Sort Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2
  3. Mục tiêu  Trình bày các thuật toán thông dụng cho việc sắp xếp trong (sắp xếp trên bộ nhớ trong - RAM)  Minh họa các thuật toán  Đánh giá thuật toán Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3
  4. Đặt vấn đề  Trong công việc hàng ngày cũng như các bài toán quản lý kinh tế cần tìm kiếm dữ liệu  Dễ dàng  Nhanh chóng  Ví dụ: danh sách sinh viên, từ điển … Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4
  5. Sắp xếp (Sorting)  Định nghĩa  Sắp xếp là quá trình tổ chức lại một tập hợp k đối tượng theo một trật tự nào đó  Hai mô hình sắp xếp  Sắp xếp trong (internal), các phần tử cần sắp xếp được lưu sẵn trong RAM  Sắp xếp ngoài (external), một số các phần tử cần sắp xếp lưu trong RAM, còn lại được lưu ở bộ nhớ ngoài Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5
  6. Các phương pháp sắp xếp cơ bản  Phương pháp sắp xếp kiểu lựa chọn  Phương pháp sắp xếp chèn  Phương pháp sắp xếp đổi chỗ Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6
  7. Phương pháp sắp xếp kiểu lựa chọn (Selection Sort)  Ý tưởng:  Tìm phần tử nhỏ nhất đem về đầu dãy  Loại phần tử này ra khỏi dãy  Tiếp tục tìm phần tử nhỏ nhất của dãy còn lại.  Thuật toán:  Ở bước thứ i ta chọn trong Ai, Ai+1, …, An phần tử có khóa nhỏ nhất và đổi chỗ với Ai.  Sau n lượt ta có dãy A được sắp thứ tự Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7
  8. Phương pháp sắp xếp kiểu lựa chọn (Selection Sort)  Ví dụ: Cho dãy số: i=7 6 4 2 3 1 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8
  9. Phương pháp sắp xếp kiểu lựa chọn (Selection Sort) public void SelectionSort() { int min,vt; for (int i = 0; i < idx-1; i++) { min = A[i]; vt = i; for (int j = i + 1; j < idx; j++) { if (A[j] < min) { min = A[j]; vt = j; } } if (vt != i) { A[vt] = A[i]; A[i] = min; } } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9
  10. Phương pháp sắp xếp chèn (Insertion Sort)  Thuật toán:  Dãy ban đầu A1,A2,…,An xem như đã có đoạn gồm 1 phần tử A1 đã được sắp.  Thêm A2 vào A1 sẽ có đoạn A1A2 đã được sắp.  Thêm A3 vào A1A2 sẽ có đoạn A1A2 A3 đã được sắp.  Tiếp tục cho đến khi thêm xong An vào đoạn A1,A2,…,An-1 sẽ có dãy A1,A2,…,An đã được sắp xếp. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10
  11. Phương pháp sắp xếp chèn (Insertion Sort)  Ví dụ:  Cho dãy số: i=2 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11
  12. Phương pháp sắp xếp chèn (Insertion Sort) i=3 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12
  13. Phương pháp sắp xếp chèn (Insertion Sort) i=4 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13
  14. Phương pháp sắp xếp chèn (Insertion Sort) i=5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14
  15. Phương pháp sắp xếp chèn (Insertion Sort) i=6 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 15
  16. Phương pháp sắp xếp chèn (Insertion Sort) i=7 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16
  17. Phương pháp sắp xếp chèn (Insertion Sort) i=8 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 17
  18. Phương pháp sắp xếp chèn (Insertion Sort) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18
  19. Phương pháp sắp xếp chèn (Insertion Sort) public void Insertion_Sort() { for (int i = 1; i < idx; i++) { int x = A[i]; int j = i - 1; while ((j >= 0)&&(A[j] > x)) { A[j + 1] = A[j]; j--; } A[j + 1] = x; } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19
  20. Phương pháp sắp xếp đổi chỗ (Bubble Sort)  Ý tưởng:  Xét từ cuối dãy ngược về vị trí i  Nếu hai phần tử kế cận ngược thứ tự thì đổi chỗ cho nhau  Thực hiện đến khi không còn phần tử để xét. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 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
2=>2