Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản

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

Thêm vào BST

Báo xấu

37
lượt xem 4
download

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

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản" thông tin đến các bạn những kiến thức về khái niệm và vai trò của sắp xếp; sắp xếp chèn; sắp xếp chọn; sắp xếp nổi bọ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 và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản

Cấu trúc dữ liệu và giải thuật Bài 5. Phương pháp sắp xếp đơn giản Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 Ngo Huu Phuc, Le Quy Don Technical University
Bài 5: Các phương pháp sắp xếp đơn giản Nội dung: 6.1. Khái niệm và vai trò của sắp xếp (13) 6.2. Sắp xếp chèn (6) 6.3. Sắp xếp chọn (4) 6.4. Sắp xếp nổi bọt (4) Tham khảo: 1. Lecture 16 Introduction to Sorting.htm 2. Data Structures and Algorithms Sorting.htm 3. Tham khảo bài giảng của TS Nguyễn Nam Hồng 2 Ngo Huu Phuc, Le Quy Don Technical University
5.1. Khái niệm và vai trò của sắp xếp 5.1.1. Các thuật toán sắp xếp. 5.1.2. Vai trò của sắp xếp. 5.1.3. Các vấn đề của sắp xếp. 5.1.4. Một số ứng dụng của sắp xếp. 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện. 5.1.6. Phân tích hiệu quả của giải thuật sắp xếp. 3 Ngo Huu Phuc, Le Quy Don Technical University
5.1.1. Các thuật toán sắp xếp (1/2)  Thế nào là sắp xếp?  Đưa một dãy các đối tượng về dạng thứ bậc nào đó.  Giải thuật sắp xếp dựa trên sự so sánh nào đó.  Việc sắp xếp chỉ dựa trên phép toán so sánh.  Các phép toán cơ bản của sắp xếp.  So sánh.  Tráo đổi giữa các phần tử. 4 Ngo Huu Phuc, Le Quy Don Technical University
5.1.1. Các thuật toán sắp xếp (1/2)  Quy ước.  Phương pháp sắp xếp của chương này là sắp xếp trong.  Các giải thuật có thể thay thế cho nhau được.  Mỗi mảng có một số phần tử.  Thành phần để xem xét trong sắp xếp có thể so sánh được.  N là số phần tử cần sắp xếp. 5 Ngo Huu Phuc, Le Quy Don Technical University
5.1.2. Vai trò của sắp xếp (1/2)  Nếu các đối tượng trong một mảng nào đó đã được sắp theo trật tự nào đó, có thể truy xuất thông tin nhanh chóng và chính xác.  Việc xây dựng giải thuật cho phép sắp xếp từng phần tử của mảng sẽ mất nhiều thời gian, độ phức tạp của giải thuật cỡ O(n2).  ≈ 50,000,000,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 500,000 giây = 58 ngày, v ới máy tính có thể thực hiện 100 triệu phép tính toán/giây.  Với giải thuật sắp xếp cho cả mảng, độ phức tạp của giải thuật cỡ O(nlogn).  ≈ 250,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 2.5 giây, với máy tính có thể thực hiện 100 triệu phép tính toán/giây. 6 Ngo Huu Phuc, Le Quy Don Technical University
5.1.2. Vai trò của sắp xếp (2/2)  Như vậy, sắp xếp là giải thuật cơ bản.  Thông thường, 25% khả năng của CPU dành cho việc sắp xếp.  Sắp xếp là bước cơ bản cho một số giải thuật khác, ví dụ: tìm kiếm nhị phân.  Có nhiều cách tiếp cận đến giải thuật sắp xếp, từ đó, có nhiều giải thuật săp xếp khác nhau. 7 Ngo Huu Phuc, Le Quy Don Technical University
5.1.3. Các vấn đề của sắp xếp  Sắp xếp theo trật tự tăng hay giảm?  Với cùng một giải thuật sắp xếp, có thể dùng cho cả sắp theo trật tăng hay giảm, bằng việc thay đổi phép so sánh: =.  Các khóa của giải thuật sắp xếp?  Có thể dùng nhiều khóa cho cùng một giải thuật sắp xếp. Cần lưu ý đến ý tưởng của bài toán.  Với các dữ liệu không phải là số thì sao?  Với chuỗi, sử dụng phép so sánh chuỗi, từ điển, hay quy tắc nào đó.  Ví dụ: Sắp chuỗi Brown-Williams, Brown America, Brown, John? 8 Ngo Huu Phuc, Le Quy Don Technical University
5.1.4. Một số ứng dụng của sắp xếp (1/2)  Với kết quả của quá trình sắp xếp, một số vấn đề có thể được thực hiện dễ dàng.  Nói chung, nếu có quá trình sắp xếp sẽ tăng tốc cho tìm kiếm trong ứng dụng cụ thể.  Ví dụ, nếu có một mảng đã sắp, có thể dễ dàng tìm được phần tử lớn thứ k trong mảng, với thời gian hằng số. 9 Ngo Huu Phuc, Le Quy Don Technical University
5.1.4. Một số ứng dụng của sắp xếp (2/2) Một số ứng dụng có dùng sắp xếp.  Các từ trong từ điển đã được sắp xếp.  Thông thường, các Files trong thư mục được sắp theo một trật tự nào đó.  Trong thư viện, các quyển sách được sắp theo một trật tự nào đó.  Các khóa học của một trường đại học được sắp theo khoa, theo mã của khóa học.  Các sự kiện được sắp theo thời gian.  … 10 Ngo Huu Phuc, Le Quy Don Technical University
5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (1/2) Có nhiều ý tưởng cho giải thuật sắp xếp:  Chèn - Insertion: đặt các phần tử vào một vị trí thích hợp của một dãy các phần tử đã sắp.  Tráo đổi - Exchange: với mỗi cặp các phần tử, tráo đổi chúng về đúng thứ tự, thực hiện cho đến khi không còn cặp nào chưa đưa về đúng thứ tự.  Chọn - Selection: chọn phần tử lớn nhất (nhỏ nhất) trong danh sách, đưa về đúng vị trí.  Phân loại - Distribution: chia nhỏ thành nhiều mảnh dựa trên tiêu chí nào đó, sau đó sắp từng mảnh.  Hợp - Merging: có thể nối 2 dãy đã sắp xếp thành 1 dãy được sắp xếp. 11 Ngo Huu Phuc, Le Quy Don Technical University
5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (2/2) Phương pháp sắp xếp:  Sắp xếp chọn:  Tìm phần tử lớn nhất (nhỏ nhất) trong số các phần tử chưa xét và đặt chúng vào đúng vị trí.  Thực hiện cho đến khi các phần tử đều được xét.  Sắp xếp chèn:  Với mỗi phần tử, chèn chúng vào mảng con đã sắp đúng trật tự.  Thực hiện tương tự cho các phần tử còn lại.  So sánh và tráo đổi – Sắp xếp nổi bọt:  Tìm 2 phần tử trong dãy không đúng trật tự, tráo đổi vị trí của chúng.  Giữ lại danh sách đã hiệu chỉnh. 12 Ngo Huu Phuc, Le Quy Don Technical University
5.1.6. Phân tích hiệu quả của giải thuật sắp xếp (1/2)  Sự hiệu quả:  Với trường hợp tồi nhất của giải thuật, độ phức tạp là thế nào?  Trong trường hợp trung bình có tốt hơn trường hợp tồi nhất không?  Yêu cầu của dữ liệu là gì?  Có thể truy xuất ngẫu nhiên được không?  Có cần thêm thao tác nào không ngoài “so sánh” và “tráo đổi”?  Không gian bộ nhớ sử dụng:  Thuật toán có cần thêm không gian phụ nào nào không? 13 Ngo Huu Phuc, Le Quy Don Technical University
5.1.6. Phân tích hiệu quả của giải thuật sắp xếp (2/2)  Tính ổn định:  Thuật toán có tính ổn định không?  Sự hiệu quả, nếu dãy đã gần sắp:  Thuật toán có hiệu quả hơn nếu như dãy đã cho gần được sắp? (nhiều phần tử đã đúng thứ tự, chỉ có một số chưa đúng thứ tự) 14 Ngo Huu Phuc, Le Quy Don Technical University
5.2. Sắp xếp chèn (1/6) Ví dụ minh họa:  Xem xét người chơi bài (sắp theo chiều giảm dần)  Quân bài thứ nhất được sắp.  Với các quân bài còn lại:  Tìm từ cuối dãy cho đến khi tìm thấy quân bài lớn hơn quân bài mới,  Di chuyển các quân bài nhỏ về sau một bậc.  Chèn quân bài mới vào vị trí đó.            A K 10 2 J 2 2 Q 9  9  15 Ngo Huu Phuc, Le Quy Don Technical University
5.2. Sắp xếp chèn (2/6)  Đây là phương pháp sắp hiệu quả nếu có ít phần tử cần sắp.  Mã lệnh cho phương pháp khá đơn giản.  Cách thức làm việc của Sắp xếp chèn.  Sử dụng biến để chia tập thành 2 vùng: vùng đẵ sắp và vùng chưa sắp.  Vùng đã sắp bắt đầu từ phần tử đầu tiên của dãy.  Lấy phần tử đầu tiên của vùng chưa sắp và chèn vào vùng đã sắp.  Như vậy, vùng đã sắp sẽ có thêm một phần tử.  Thực hiện tương tư cho đến khi vùng chưa sắp không còn phần tử nào. 16 Ngo Huu Phuc, Le Quy Don Technical University
5.2. Sắp xếp chèn (3/6) Giả sử: Sắp xếp dãy các số nguyên theo Chuỗi đã sắp Phần tử sẽ được chèn phương pháp chèn. 8 5 2 6 9 4 6 Giá trị 5 nhỏ hơn 8, 5 sẽ thay thế cho 8, dãy đã sắp sẽ có kích thước tăng lên 1 (có 2 phần tử đã được sắp. Hoạt động của Insertion Sort 5 8 2 6 9 4 6 17 Ngo Huu Phuc, Le Quy Don Technical University
5.2. Sắp xếp chèn (4/6) #include void inputdata(int* list,int n) #include { #define MAX 100 int i; void inputdata(int* list,int n); printf("Nhap cac phan tu cua mang\n"); void printlist(int* list,int n); for(i=0;i
5.2. Sắp xếp chèn (5/6) void insertionsort(int *list, int n) { int pos,i,x; for(i=1;i=0) && (list[pos]>x)) { list[pos+1]=list[pos]; pos--; } list[pos+1]=x; } } 19 Ngo Huu Phuc, Le Quy Don Technical University
5.2. Sắp xếp chèn (6/6) Phân tích sắp xếp chèn:  Trường hợp tồi nhất:  Với dữ liệu dạng nào cho kết quả tồi nhất?  Dữ liệu được sắp theo chiều ngược lại.  Độ phức tạp trong trường hợp này?  O(N2) – phép so sánh: N2, phép tráo đổi: N2  Trường hợp tốt nhất:  Với dữ liệu dạng nào cho kết quả tốt nhất?  Dữ liệu đã được sắp.  Độ phức tạp trong trường hợp này?  O(N) – phép so sánh: N, phép tráo đổi: none  Trường hợp trung bình:  Với dữ liệu dạng nào cho kết quả trung bình?  Dữ liệu dạng ngẫu nhiên.  Độ phức tạp trung bình?  O(N2) – phép so sánh: N2, phép tráo đổi: N2 20 Ngo Huu Phuc, Le Quy Don Technical University