Bài giảng Hệ thống thông tin - Các thuật toán sắp xếp

Nội dung text: Bài giảng Hệ thống thông tin - Các thuật toán sắp xếp

1. Giới thiệu Các thuật toán sắp xếp 08/02/2014 1
2. Nội dung trình bày • Bài toán sắp xếp • Tiếp cận sắp xếp đơn giản ° Sắp xếp chọn ° Sắp xếp chèn ° Sắp xếp nổi bọt • Tiếp cận sắp xếp độ phức tạp O(nlog(n)) ° Sắp xếp theo phân đoạn (Quick sort) ° Sắp xếp hòa nhập ° Sắp xếp vung đống • Một số tiếp cận khác ° Sắp xếp theo cơ số 08/02/2014° Sắp xếp hòa nhập hai file lớn 2
3. Bài toán sắp xếp • Cho một dãy dữ liệu có thể so sánh được (theo tiêu chí so sánh) • Sắp xếp các phần tử mảng theo thứ tự (không giảm, không tăng) • Ví dụ: ° Cho danh sách các mức xám của các điểm ảnh: sắp xếp theo thứ tự không tăng của các mức xám ° Cho danh sách sinh viên: sắp xếp sinh viên theo thứ tự không giảm theo ngày sinh 08/02/2014 3
4. Đánh giá ứng dụng • Tính ứng dụng: ° Bài toán lựa chọn theo thứ tự nào đó là bài toán sắp xếp theo tiêu chí ° Nhiều thuật toán thực hiện hiệu quả trên những bộ dữ liệu đã được sắp xếp theo xu hướng • Đặc điểm ° Phải có tiêu chí so sánh lớn hơn, bé hơn được ° Có thể so sánh một số thành phần của đối tượng để xác định tiêu chí ° Tính hiệu quả thuật toán phụ thuộc vào độ phức tạp của phép so sánh và hoán đổi vị trí ° Một số thuật toán độ phức tạp về bộ nhớ cũng là 08/02/2014vấn đề trong dữ liệu lớn 4
5. Phân loại theo độ phức tạp • Thuật toán đơn giản O(n2) ° Sắp xếp chọn ° Sắp xếp chèn ° Sắp xếp nổi bọt • Sắp xếp theo phương pháp chia để trị O(nlog(n)) ° Sắp xếp phân đoạn ° Sắp xếp trộn ° Sắp xếp vun đống • Sắp xếp theo phương pháp O(n) ° Sắp xếp theo cơ số 08/02/2014 5
6. Sắp xếp chọn – selection sort - Sắp xếp dãy không giảm - 1 7 3 8 2 6 4 1 2 3 4 6 7 8 08/02/2014 6
7. Sắp xếp chọn (t) • Ý tưởng ° Chọn phần tử bé nhất đổi chổ đưa lên đầu ° Tiếp theo chọn phần tử bé thứ 2 đưa lên vị trí thứ hai ° Chọn phần tử bé thứ k đưa đến vị trí thứ k ° Lặp lại đến phần tử thứ N-1 08/02/2014 7
8. Sắp xếp chọn (t) • Phát biểu lại ° Chọn phần tử bé nhất đổi chổ đưa lên đầu ° Giả sử có k phần tử ở đầu đã được sắp xếp ° Tìm phần tử bé nhất từ k+1 đến n, đổi chổ cho phần tử tại k+1. ° Lặp tương tự cho đến phần tử N-1 08/02/2014 8
9. Sắp xếp chọn (t) • Thuật toán ° Input: A[0 N-1] ° Output: A[0 N-1] đã được sắp xếp không giảm 1. for i=0->N-2 a. vt=i; b. for j=i+1->N-1 if (a[j]<a[vt]) vt=j; c. if(i!=vt) swap(a[i],a[vt]); 08/02/2014 9
10. Sắp xếp chọn (t) • Thực hiện từng bước i vt 0 1 2 3 4 5 6 0 0 1 7 3 8 2 6 4 1 4 1 7 3 8 2 6 4 2 2 1 2 3 8 7 6 4 3 6 1 2 3 8 7 6 4 4 5 1 2 3 4 7 6 8 5 5 1 2 3 4 6 7 8 08/02/2014 10
11. Sắp xếp chọn (t) • Độ phức tạp ° Số phép toán so sánh: N(N-1)/2 + N ° Số phép toán gán chỉ số: N(N-1)/2 +N ° Số phép gán giá trị phần tử: 3*(N-1) ° Độ phức tạp là O(n 2) 08/02/2014 11
12. Sắp xếp chèn - insertion sort • Ý tưởng ° Dựa trên ý tưởng việc sắp xếp quân bài ° Chèn những quân bài đang cầm (xem xét) vào vị trí thích hợp ° Ban đầu chỉ có một quân bài ° Sau đó thêm các quân bài mới thì chèn quân bài đó vào vị trí thích hợp 08/02/2014 12
13. Sắp xếp chèn (t) • Ý tưởng ° Xét mảng chỉ có phần tử - đã được sắp xếp ° Mảng có k-1 phần tử đã được sắp xếp ° Xét thêm phần tử thứ k (giá trị x) vào mảng trên ° Xét từ vị trí k -1 đến đầu nếu các gặp phần tử lớn hơn x thì dịch phần tử đó về sau một ô ° Gán giá trị x vào vị trí dịch chuyển tạo ra 08/02/2014 13
14. Sắp xếp chèn (t) • Thuật toán ° Input: A[0 N-1] phần từ ° Ouput: A[0 N-1] đã được sắp xếp không giảm 1. for i=1->N-1 a. x=A[i]; b. vt=i; c. while (vt>0 && A[vt-1]>x) A[vt]=A[vt-1]; vt ; d. A[vt]=x; 08/02/2014 14
15. Sắp xếp chèn (t) i vt 0 1 2 3 4 5 6 1 1 1 7 3 8 2 6 4 2 1 1 7 3 8 2 6 4 3 3 1 3 7 8 2 6 4 4 1 1 3 7 8 2 6 4 5 3 1 2 3 7 8 6 4 6 3 1 2 3 6 7 8 4 1 2 3 4 6 7 8 08/02/2014 15
16. Sắp xếp chèn (t) • Độ phức tạp thuật toán ° Số phép so sánh N(N-1)/2 ° Số phép gán giá trị phần tử: N(N-1)+2N ° Số phép gán chỉ số: N(N-1) ° Độ phức tạp thuật toán O(n 2) 08/02/2014 16
17. Sắp xếp nổi bọt - bubble sort • Dựa trên ý tưởng về các bọt khí trong cốc bia • Hai bọt khí cạnh nhau thì bọt lớn hơn sẽ nổi lên trên • Đến khi không còn bọt khí nào trái quy luật đó thì các bọt khí đã được sắp xếp 08/02/2014 17
18. Sắp xếp nổi bọt (t) • Ý tưởng ° Xét hai phần tử ở đầu tiên của dãy, nếu không đúng thứ tự đổi chỗ cho nhau ° Tiếp tục xét các cặp đến cuối dãy ° Lặp lại quá trình với cặp đầu dãy đến lúc không có cặp nào bị thay đổi 08/02/2014 18
19. Sắp xếp nổi bọt (t) • Thuật toán • Input: A[0 N-1] phần tử • Output: A[0 N-1] phần tử sắp xếp không giảm 1. for i=N-1 -> 1 a. for j=0 ->i -1 if(a[j]>a[j+1]) swap(a[j],a[j+1]); 08/02/2014 19
20. Sắp xếp nổi bọt (t) i j 0 1 2 3 4 5 6 6 1 1 7 3 8 2 6 4 6 3 1 3 7 8 2 6 4 6 4 1 3 7 2 8 6 4 6 5 1 3 7 2 6 8 4 5 2 1 3 7 2 6 4 8 5 3 1 3 2 7 6 4 8 5 4 1 3 2 6 7 4 8 4 1 1 3 2 6 4 7 8 4 3 1 2 3 6 4 7 8 1 2 3 4 6 7 8 08/02/2014 20
21. Sắp xếp nổi bọt (t) • Độ phức tạp thuật toán ° Số phép toán so sánh N(N-1)/2 ° Số phép toán gán 3(N)(N-1)/2 ° Độ phức tạp thuật toán O(n 2) 08/02/2014 21
22. Nhận xét • So sánh độ phức tạp thuật toán của ba thuật toán trên ° Theo đánh giá chung ° Đánh giá theo các tiêu chí • Số phép so sánh • Số phép gán dữ liệu • Số phép gán chỉ số 08/02/2014 22
23. Nhận xét • Nhìn chung ba thuật toán có độ phức tạp tương đương vì thế thời gian thực hiện là tương đương nhau • Thực tế ° Sự phức tạp của so sánh, phép gán, phép gán chỉ số là không giống nhau với các kiểu dữ liệu khác nhau (Ví dụ) 08/02/2014 23
24. Nhận xét • Thuật toán chọn, nổi bọt có thể chọn được k phần tử đứng đầu, hoặc cuối trong N phần tử mà không cần phải sắp xếp toàn bộ các phần tử (Ví dụ) • Thuật toán sắp xếp chèn, nổi bọt phù hợp với hệ thống duy trì tính sắp xếp với dữ liệu thêm và bớt thường xuyên mà không phải sắp xếp lại toàn bộ (ví dụ) 08/02/2014 24
25. Thảo luận • Đánh trường hợp xấu nhất, tốt nhất ° Chọn ° Chèn ° Nổi bọt 08/02/2014 25
26. Thảo luận • Trong trường hợp cho một dãy N phần tử đã sắp xếp, cần thêm M phần tử vào dãy 08/02/2014 26
27. Thảo luận • Thảo luận về tính ổn định thứ tự của các thuật toán ° Các phần tử có cùng giá trị so sánh giữ nguyên thứ tự 08/02/2014 27
28. Nội dung trình bày • Bài toán sắp xếp • Tiếp cận sắp xếp đơn giản ° Sắp xếp chọn ° Sắp xếp chèn ° Sắp xếp nổi bọt 08/02/2014 28
29. Bài tập trên lớp • Sinh viên thực hiện các thuật toán với bộ dữ liệu • 1 6 4 7 3 9 3 08/02/2014 29
30. Bài tập - Cài đặt thuật toán trên ngôn ngữ lập trình và chạy thử - Thử nghiệm các thuật toán sắp xếp để đạt được dãy không tăng với các bộ dữ liệu sau - 1 2 3 4 5 6 - 6 5 4 3 2 1 - 5 2 6 4 1 3 - Nhận xét trong trường hợp nào thuật toán nào thực hiện nhiều thao tác nhất (đâu là trường hợp tốt nhất, xấu nhất) và số thao tác trong trường hợp đó - Trong trường hợp độ phức tạp của phép chuyển chổ và so sánh là khác nhau thì sắp xếp nào tốt hơn, ngược lại. 08/02/2014 30