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

Sắp xếp - Sorting

Chia sẻ: Nguyễn Thị Phương Phương | Ngày: | Loại File: PPT | Số trang:28

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

Ta khảo sát trường hợp xấu nhất, trung bình và tốt nhất cho mỗi giải thuật. Thời gian thực hiện thay đổi dựa vào sự phân bố ban đầu của dãy.

Chủ đề:

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

Lưu

Nội dung Text: Sắp xếp - Sorting

  1. Đặt vấn đề • Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định • Mục đích của sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu được dễ dàng nhanh chóng • Ví dụ:  Cho trước một dãy n số nguyên được sắp thứ tự tăng dần  Việc tìm kiếm một phần tử x nào đó được thực hiện bằng cách chia đôi dãy ban đầu  Chỉ cần k bước ta xác định được phần tử cần tìm
  2. Đặt vấn đề  Trường hợp xấu nhất  Vậy với n = 1000 ≈ 210 i.e chỉ cần 10 bước là ta xác định được phần tử cần tìm trong dãy 1000 phần tử  n = 1.000.000 ≈ 220  n = 1 tỷ ≈ 230  Rõ ràng sắp xếp là một việc làm hết sức cơ bản và được áp dụng rộng rãi trong các kỹ thuật lập trình nhằm xử lý thông tin.
  3. Sorting Nội dung – Định nghĩa – Giả thiết – Sắp xếp tại chỗ – Chiến lược sắp xếp – Tổng quan về thời gian thực hiện
  4. Sorting Định nghĩa • Sắp xếp là một tiến trình: – Tìm một bộ hoán vị trên tập hợp các đối tượng cho trước a1, a2, ..., an (ví dụ là các số nguyên), và – Trả về một thứ tự khác (a'1, a'2, ..., a'n) sao cho a'1 ≤ a'2 ≤ · · · ≤ a'n
  5. Sorting Định nghĩa • Ít khi ta sắp xếp các giá trị đơn lẻ. • Thông thường chúng ta sắp xếp một số các mẫu tin chứa một số các trường trên cơ sở trường khóa 19991532 Stevenson Monica 3 Glendridge Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19985832 Kilji Islam 37 Masterson Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19989932 Carol Ann 81 Oakridge Ave. 20003287 Redpath David 5 Glendale Ave. Theo ID number 19989932 Carol Ann 81 Oakridge Ave. Theo thứ tự họ tên 19985832 Kilji Islam 37 Masterson Ave. 19989932 Carol Ann 81 Oakridge Ave. 19990253 Redpath Ruth 53 Belton Blvd. 20003541 Groskurth Ken 12 Marsdale Ave. 19991532 Stevenson Monica 3 Glendridge Ave. 19985832 Kilji Islam 37 Masterson Ave. 20003287 Redpath David 5 Glendale Ave. 20003287 Redpath David 5 Glendale Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19991532 Stevenson Monica 3 Glendridge Ave.
  6. Sorting Định nghĩa • Trong phần này, ta giả sử rằng: – Mảng đựợc sử dụng cho cả input và output – Tập trung sắp xếp trường khóa và để lại mọi trường h ợp tổng quát ở phần cài đặt,và – Các đối tượng sắp xếp là duy nhất, i.e., các đối tượng đã sắp xếp lại sẽ thỏa điều sau: a'1 < a'2 < · · · < a'n
  7. Sorting Sắp tại chỗ (in-place) • Giải thuật được sắp tại chỗ nghĩa là việc xin cấp phát vùng nhớ chỉ dành cho một số biến cục bộ mà thôi. • Một số giải thuật khác cần cấp phát mảng phụ thứ hai có cùng kích thước với mảng ban đầu (cần O(n) bộ nhớ bổ sung)
  8. Sorting Phân loại • Nhiều giải thuật sắp xếp chỉ được phân loại qua các thao tác thực hiện: Chèn Hoán đổi Chọn Trộn Phân phối
  9. Sorting Run-time • Thời gian thực hiện giải thuật rơi vào 3 nhóm chính: O(n) O(n ln(n)) O(n2) • Ta khảo sát trường hợp xấu nhất, trung bình và tốt nhất cho mỗi giải thuật • Thời gian thực hiện thay đổi dựa vào sự phân bố ban đầu của dãy.
  10. Sorting Run-time • Ta sẽ khảo sát một số giải thuật cổ điển có độ phức tạp O(n2) : – insertion sort, bubble sort • Một số giải thuật chạy nhanh hơn O(n ln(n)) : – heap sort, quick sort, và merge sort
  11. Sorting Cận dưới • Bất kỳ một giải thuật sắp xếp nào cũng phải khảo sát từng phần tử ít nhất 1 lần • Kết luận, mọi giải thuật phải có cận dưới là Ω (n)
  12. Sorting Định nghĩa về nghịch thế • Xét 3 dãy sau: 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 • 3 dãy này chưa được sắp xếp ở mức độ nào ?
  13. Sorting Định nghĩa về nghịch thế • Dãy đầu tiên chỉ cần một ít sự hóan đổi là đủ để sắp xếp lại dãy này. 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 12 16 25 26 33 35 42 45 56 58 67 74 75 81 83 86 88 95 99
  14. Sorting Định nghĩa về nghịch thế • Dãy thứ hai có hai phần tử nằm rất xa vị trí đúng 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 1 17 21 23 24 27 32 35 42 45 47 57 66 69 70 76 85 87 95 99 • Tuy nhiên có 13 phần tử đã đúng vị trí
  15. Sorting Định nghĩa về nghịch thế Dãy thứ ba, hầu hết các vị trí đều không đúng vị trí của nó 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 1 10 12 16 20 22 26 31 38 44 48 79 80 81 84 87 92 95 96 99
  16. Sorting Định nghĩa về nghịch thế • Cho trước một dãy bất kỳ có n phần tử, ta có  n  n(n − 1)  =  2 cặp số   2 • Ví dụ, dãy 1, 3, 5, 4, 2, 6 chứa 15 cặp số sau (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)
  17. Sorting Định nghĩa về nghịch thế • Lưu ý rằng 11 cặp trong số các cặp này đã có thứ tự: (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)
  18. Sorting Định nghĩa về nghịch thế • Trong khi 4 cặp còn lại có thứ tự ngược (1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)
  19. Sorting Định nghĩa về nghịch thế • Xét tập các phần tử S • Một hoán vị của S là sự tái sắp xếp các phần tử trong S • Ví dụ: S = {0, 1, 2, 3}, có 4! = 24 phép hoán vị như sau: 0123 0132 0213 0231 0312 0321 1023 1032 1203 1230 0312 0321 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120 3201 3210
  20. Sorting Định nghĩa về nghịch thế • Do đó , phép hoán vị sau 1, 3, 5, 4, 2, 6 chứa 4 nghịch thế: (3, 2) (5, 4) (5, 2) (4, 2)
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2418 lượt tải
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