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: Các giải thuật sắp xếp - Lê Thị Ngọc Hạnh

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:40

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

Chương này trình bày một số nội dung chính như: giới thiệu bài toán sắp xếp, các phương pháp sắp xếp, đổi chỗ trực tiếp – interchange sort, interchange sort – thuật toán, interchange sort – cài đặt, interchange sort – đánh giá, sắp xếp chọn – selection sort, selection sort – ý tưởng,... Mời các bạn cùng tham khảo.

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: Các giải thuật sắp xếp - Lê Thị Ngọc Hạnh

  1. CÁC GIẢI THUẬT SẮP XẾP GV: LÊ THỊ NGỌC HẠNH 1 9/4/2015 Data structure & Algorithms
  2. GIỚI THIỆU BÀI TOÁN SẮP XẾP  Bài toán sắp xếp: Là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.  Lưu ý: Thứ tự đề cập ở đây là một thứ tự tổng quát.  Ví dụ: Danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40} 9/4/2015 Data structure & Algorithms 2
  3. GIỚI THIỆU BÀI TOÁN SẮP XẾP  Khái niệm “Nghịch thế” Xét một mảng các số a0, a1, …, an Nếu có iaj thì ta gọi đó là một nghịch thế. Mảng chưa sắp xếp sẽ có nghịch thế Mảng đã có thứ tự sẽ không chứa nghịch thế 9/4/2015 Data structure & Algorithms 3
  4. CÁC PHƯƠNG PHÁP SẮP XẾP  Selection sort  Quick sort  Insertion sort  Merge sort  Interchange sort  Radix sort Shaker sort  Bubble sort  Radix sort  Shaker sort …  Binary Insertion sort … 9/4/2015 Data structure & Algorithms 4
  5. ĐỔI CHỖ TRỰC TIẾP – INTERCHANGE SORT  Ý tưởng: Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này triệt tiêu chúng bằng cách đổi chỗ phần tử này tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. 9/4/2015 Data structure & Algorithms 5
  6. INTERCHANGE SORT – THUẬT TOÁN Bước 1: Khởi tạo i=0 // bắt đầu từ đầu dãy Bước 2: j = i+1; //tìm các cặp a[j]I Bước 3: Trong khi j
  7. INTERCHANGE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 7
  8. INTERCHANGE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 8
  9. INTERCHANGE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 9
  10. INTERCHANGE SORT – CÀI ĐẶT Void InterchangeSort(int a[], int n) { int i, j; for(i = 0 ; i
  11. INTERCHANGE SORT – ĐÁNH GIÁ Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu. Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh 9/4/2015 Data structure & Algorithms 11
  12. SẮP XẾP CHỌN – SELECTION SORT 9/4/2015 Data structure & Algorithms 12
  13. SELECTION SORT – Ý TƯỞNG  Chọn phần tử nhỏ nhất đặt vào vị trí đầu tiên  Chọn phần tử nhỏ nhất trong số n-1 phần tử còn lại đặt vào vị trí thứ 2.  Lặp lại quá trình cho đến khi mảng chỉ còn 1 phần tử. 9/4/2015 Data structure & Algorithms 13
  14. SELECTION SORT – THUẬT TOÁN  Bước 1: Khởi tạo i = 0.  Bước 2: Khởi đầu min = i, j = i+1  Bước 3: Nếu a[j]
  15. SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 15
  16. SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 16
  17. SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 17
  18. SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 18
  19. SELECTION SORT – CÀI ĐẶT void SelectionSort(int a[],int n) { int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for(int i=0; i
  20. SELECTION SORT – ĐÁNH GIÁ Số phép so sánh:  Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh  Không phụ thuộc vào tình trạng dãy số ban đầu  Số phép so sánh: 9/4/2015 Data structure & Algorithms 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