Sắp xếp - Sorting ! ! ! Trình bày các thuật toán thông dụng cho việc sắp xếp

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:52

Thêm vào BST

Báo xấu

214
lượt xem 44
download

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

Sắp xếp - Sorting ! ! ! Trình bày các thuật toán thông dụng cho việc sắp xếp nội (sắp xếp trên bộ nhớ trong - Mảng) Minh họa các thuật toán Đánh giá thuật toán Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1 Nội dung trình bày ! ! ! ! ! ! Thuật toán “Selection sort” Thuật toán “Insertion sort” Thuật toán “Shell sort” Thuật toán “Heap sort” Thuật toán “Merge sort” Thuật toán “Quick sort” Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 1 Sắp xếp 1 mảng các số nguyên ! Giả sử có...

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 ! ! ! Trình bày các thuật toán thông dụng cho việc sắp xếp

Sắp xếp - Sorting Trình bày các thuật toán ! thông dụng cho việc sắp xếp nội (sắp xếp trên bộ nhớ trong - Mảng) Minh họa các thuật toán ! Đánh giá thuật toán ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 1 Nội dung trình bày Thuật toán “Selection sort” ! Thuật toán “Insertion sort” ! Thuật toán “Shell sort” ! Thuật toán “Heap sort” ! Thuật toán “Merge sort” ! Thuật toán “Quick sort” ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 2 1
Sắp xếp 1 mảng các số nguyên Giả sử có 1 ! mảng gồm 6 70 số nguyên. 60 Ta cần sắp 50 xếp các phần 40 tử của mảng 30 theo thứ tự 20 tăng dần 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 3 Thuật toán “Chọn trực tiếp” (Selection sort Algorithm) Bắt đầu bằng ! cách tìm 70 phần tử nhỏ 60 nhất 50 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 4 2
Selection sort Algorithm Hoán vị ! phần tử nhỏ 70 nhất tìm 60 được với 50 phần tử đầu 40 tiên của 30 mảng 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 5 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 1 phần của 60 ! mảng đã 50 được sắp xếp 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 6 3
Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 Tìm phần tử 60 ! nhỏ nhất 50 trong phần 40 chưa được 30 sắp 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 7 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 Hoán vị ! 60 phần tử nhỏ 50 nhất trong 40 phần chưa 30 được sắp với 20 phần tử đầu 10 tiên trong 0 phần này [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 8 4
Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 Phần đã ! 60 được sắp xếp 50 của mảng 40 được tăng 30 thêm 1 phần 20 tử 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 9 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 Tiếp tục ! 60 tương tự ... Phần tử 50 nhỏ nhất 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 10 5
Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 Tiếp tục ! 60 ị tương tự ... nv á 50 Ho hần p với đầu 40 tử 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 11 Selection sort Algorithm Phần đã sắp Phần đã sắp Phần chưa sắp tăng thêm 70 Tiếp tục ! 60 tương tự ... 50 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 12 6
Selection sort Algorithm Phần đã sắp Phần chưa sắp Quá trình lần ! lượt thêm từng 70 phần tử vào 60 phần đã sắp… 50 Phần đã sắp ! 40 chứa các phần 30 tử nhỏ nhất, sắp 20 tăng dần 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 13 Selection sort Algorithm Phần đã sắp Phần chưa … Thuật toán ! dừng khi chỉ 70 còn 1 phần tử 60 (đó là phần tử 50 lớn nhất). 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 14 7
Selection sort Algorithm Toàn bộ mảng ! đã được sắp thứ 70 tự. 60 Tổng quát: chọn 50 ! phần tử nhỏ nhất 40 và đưa nó về vị 30 trí đầu của phần 20 chưa được sắp 10 trong mảng. 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 15 Selection sort Algorithm (Minh họa chương trình) void SelectionSort (int a[ ], int n ) { // vị trí của phần tử nhỏ nhất (trong phần chưa sắp) int min; // biến tạm dùng khi hoán vị int tmp; for (int i = 0; i < n; i++ ) { // tìm phần tử nhỏ nhất trong phần chưa sắp min = i; for (int j = i + 1; j < n; j++) if (a[j] < a[min] ) min = j; // hoán vị phần tử nhỏ nhất được tìm thấy với phần tử đầu if (a[min] < a[i]) { tmp = a[i]; a[i] = a[min]; a[min] = tmp; } } // end of for i } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 16 8
Đánh giá thuật toán (Selection sort Algorithm) Trong mọi trường hợp, số phép so sánh là: ! (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) Số phép hoán vị: ! Trường hợp xấu nhất: O(n) ! Trường hợp tốt nhất (mảng đã sắp tứ tự tăng ! dần): 0 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 17 Thuật toán “Chèn trực tiếp” (Insertion sort Algorithm) Thuật toán ! “Chèn trực 70 tiếp” cũng 60 chia mảng 50 thành 2 40 phần: phần 30 đã được sắp 20 và phần 10 chưa được 0 sắp [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 18 9
Insertion sort Algorithm Phần đã sắp Phần chưa sắp Phần đã sắp 70 ! lúc đầu chỉ 60 có 1 phần 50 tử đầu tiên 40 của mảng 30 (không cần 20 thiết là phần 10 tử nhỏ nhất) 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 19 Insertion sort Algorithm Phần đã sắp Phần chưa sắp 70 Mở rộng ! 60 phần đã sắp bằng cách 50 40 thêm vào phần tử đầu 30 20 tiên trong phần chưa 10 được sắp… 0 [1] [2] [3] [4] [5] [5] [6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 20 10
Insertion sort Algorithm Phần đã sắp Phần chưa sắp ...và đặt nó 70 ! vào vị trí 60 thích hợp, 50 sao cho phần 40 đã sắp vẫn 30 giữ nguyên 20 tính thứ tự 10 (tăng dần). 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 21 Insertion sort Algorithm Phần đã sắp Phần chưa sắp Trong ví dụ 70 ! này, phần tử 60 mới được 50 đặt vào vị trí 40 đầu của 30 phần đã sắp. 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 22 11
Insertion sort Algorithm Phần đã sắp Phần chưa sắp Đôi khi 70 ! 60 chúng ta “gặp may”, 50 phần tử mới 40 không cần 30 phải di 20 chuyển. 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 23 Insertion sort Algorithm Phần đã sắp Phần chưa sắp … và lại 70 ! “gặp may” 60 thêm 1 lần 50 nữa.. 40 30 20 10 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 24 12
Insertion sort Algorithm Làm sao để chèn 1 phần tử ? Copy phần Phần đã sắp Phần chưa sắp ! tử mới vào 1 70 biến trung 60 gian… 50 40 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 25 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …Dịch ! chuyển các 70 phần tử 60 trong phần 50 đã sắp sang 40 phải… 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 26 13
Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …để tạo 1 ! chỗ trống 70 cho phần tử 60 mới… 50 40 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 27 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …tiếp tục ! dịch chuyển 70 các phần 60 tử... 50 40 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 28 14
Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …tiếp tục ! dịch chuyển 70 các phần 60 tử... 50 40 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 29 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? ...cho đến ! khi tìm thấy 70 vị trí thích 60 hợp cho 50 phần tử 40 mới... 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 30 15
Insertion sort Algorithm Làm sao để chèn 1 phần tử ? Copy phần Phần đã sắp Phần chưa… ! tử mới vào 70 lại mảng, tại 60 vị trí này. 50 40 30 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 31 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? Phần đã sắp Phần chưa… Phần tử cuối ! cùng cũng 70 phải “chèn”. 60 Copy nó vào 50 1 biến trung 40 gian... 30 20 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 32 16
Insertion sort Algorithm Câu hỏi ? Có bao nhiêu phép dịch 70 chuyển xảy 60 ra ? 50 40 30 20 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 33 Insertion sort Algorithm Câu hỏi ? Có 4 phép ! dịch chuyển 70 … 60 50 40 30 20 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 34 17
Insertion sort Algorithm !… Copy phần tử trở 70 lại mảng. 60 50 40 30 20 20 10 10 0 0 [1] [2] [3] [4] [5] [5][6] [0] [1] [2] [3] [4] Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 35 Insertion sort Algorithm (Minh họa chương trình) void InsertionSort (int a[ ], int n) { int saved; // biến trung gian lưu lại giá trị phần tử cần chèn for (int i = 1; i < n; i++ ) { // lưu lại giá trị phần tử cần chèn saved = a[i]; // dịch chuyển các phần tử trong phần đã sắp sang phải for (int j = i; j > 0 && saved < a[j-1]; j--) a[j] = a[j-1]; // chèn phần tử vào đúng vị trí a[j] = saved; } // end of for i } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 36 18
Đánh giá thuật toán (Insertion sort Algorithm) Trường hợp xấu nhất có: ! 1 + 2 + 3 + … + (n-1) = n(n-1)/2 = O(n2) phép so sánh và dịch chuyển Trường hợp tốt nhất (mảng đã có thứ tự ! tăng dần): O(n) phép so sánh và 0 phép dịch chuyển Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 37 Nhận xét chung (Selection & Insertion sort) “Chèn trực tiếp” và “Chọn trực tiếp” đều có ! chi phí cho trường hợp xấu nhất là O(n2) Do đó, không thích hợp cho việc sắp xếp các ! mảng lớn Dễ cài đặt, dễ kiểm lỗi ! “Chèn trực tiếp” tốt hơn “Chọn trực tiếp”, ! nhất là khi mảng đã có thứ tự sẵn Cần có những thuật toán hiệu quả hơn cho ! việc sắp xếp các mảng lớn Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 38 19
Thuật toán “Shell sort” (Shell sort Algorithm) Được đề xuất vào năm 1959 bởi Donald ! Shell trên tạp chí Communication of the ACM Thuật toán này cải tiến hiệu quả của thuật ! toán “Chèn trực tiếp” Phá vỡ rào cản chi phí O(n2) của những ! thuật toán sắp xếp trước đó Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 39 Shell sort Algorithm Ý tưởng: ! Chia dãy ban đầu thành h dãy con ! a0, a0+h, a0+2h, … a1, a1+h, a1+2h, … a2, a2+h, a2+2h, … … Sắp xếp từng dãy con bằng cách sử dụng ! phương pháp “Chèn trực tiếp” Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 40 20