Thuật toán BubbleSort

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

Thêm vào BST

Báo xấu

63
lượt xem 4
download

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

Xác định thời gian chạy trung bình thì khó hơn, do ta không chắc chắn khi nào giải thuật kết thúc. Ta cần một cách khác cho phép ta đếm được số các hoán đổi xảy ra.

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán BubbleSort

Nội dung • Giải thuật thứ hai có độ phức tạp O(n2) là Bubble sort – Áp dụng chiến lược ngược với insertion sort • Ta sẽ khảo sát: – Giải thuật và ví dụ minh họa – Thời gian thực hiện • Trường hợp xấu nhất • Tốt nhất • Trung bình (giới thiệu về nghịch thế) – Tổng kết và thảo luận
Bubble Sort • Giả sử ta có dãy dữ liệu chưa được sắp: – Xuất phát từ đầu, duyệt trên dãy,tìm phần tử lớn nhất, nổi bọt nó (bubble) về đỉnh. – Với mỗi bước lặp tiếp theo, tìm phần tử lớn nhất kế tiếp và bubble nó về hướng đỉnh của dãy.
Bubble Sort • Bắt đầu từ phần tử đầu tiên, giả sử rằng đây là phần tử lớn nhất. • So sánh nó với phần tử thứ hai: – Nếu phần tử thứ nhất lớn hơn, hoán đổi hai phần tử – Ngược lại, ta giả sử rằng phần tử thứ hai là phần tử lớn nhất • Tiếp tục đi về cuối dãy, hoặc là hoán đổi hoặc là định nghĩa lại phần tử lớn nhất.
Bubble Sort • Sau một lần duyệt, phần tử lớn nhất phải ở vị trí cuối cùng của dãy. • Bắt đầu lại từ đầu: – Lần duyệt thứ hai sẽ đem phần tử lớn thứ hai về vị trí cuối cùng thứ hai của dãy • Lặp lại n – 1 lần, sau đó, mọi phần tử sẽ ở đúng vị trí của nó.
Bubble Sort: minh họa • Hãy xem dãy chưa được sắp bên tay phải. • Chúng ta bắt đầu từ phần tử đầu tiên và di chuyển xuôi xuống: – Nếu phần tử hiện hành và phần tử kế có thứ tự , tiếp tục với phần tử tiếp theo; nếu ngược lại – Hoán đổi hai phần tử
Bubble Sort: minh họa • Sau một lần lặp, phần tử lớn nhất đã ở vị trí cuối cùng của dãy • Lặp lại tiến trình
Bubble Sort: minh họa • Hiện tại hai phần tử lớn đã nằm ở cuối dãy • Lặp lại tiến trình 5 12
Bubble Sort: minh họa • Sau cùng, chúng ta hoán đổi hai vị trí cuối để sắp thứ tự chúng. Đến đây, ta đã có dãy được sắp
Bubble Sort: Cài đặt void BubbleSort(int array[] , int n ) { for (int i=n-1 ; i>0 ; i-- ) for ( int j=0 ; j array[j+1] ) Swap ( array[j] , array[j+1] ) ; }
Phân tích giải thuật Trường hợp xấu nhất • Vòng lặp đầu tiên ta phải mất n – 1 phép so sánh • Số lần hoán đổi nhiều nhất cũng chỉ là n – 1. • Tổng các phép so sánh là: n −1 ( n − 1) n ∑k =1 n − k = n ( n − 1) − 2
Phân tích giải thuật Trường hợp xấu nhất • Kết luận, trường hợp xấu nhất của bubble sort là O(n2) . • Trường hợp trung bình thì không khác: dạng của giải thuật cần O(n2) phép so sánh • Thông thường sau một số hữu hạn bước ta nhận thấy dãy đã có thứ tự.
Bubble Sort có cờ • Xét một biến thể của giải thuật như sau: – Với mỗi bước ta duy trì một cái cờ để ghi nhận có sự hoán đổi xảy ra hay không ? • Nếu không có sự hoán đổi xảy ra, khi đó từng cặp phần tử trong dãy đã có thứ tự, do đó toàn bộ dãy đã được sắp. – Có thể chứng minh điều này bằng qui nạp
Bubble Sort có cờ: Cài đặt void FlaggedBubbleSort(int array[], int n ) { int i = n-1 ; char ok ; do { ok = 0 ; // false for ( j = 0 ; j < i ; j++ ) if ( array[j] < array[j+1] ) { Swap (array[j], array[j+1]); ok = 1 //true } i-- ; } while (ok) ; }
Phân tích Flagged Bubble Sort trường hợp tốt nhất • Giả sử rằng dãy đã được sắp. • Tình huống này, sau một lần duyệt, không có sự hoán đổi xảy ra, giải thuật kết thúc. • Do đó, thời gian chạy trong trường hợp này là O(n).
Phân tích Flagged Bubble Sort trường hợp xấu nhất • Giả sử rằng dãy có thứ tự ngược. • Tình huống này, mỗi phép so sánh cần một sự hoán đổi, do đó giải thuật không thể kết thúc sớm được. • Thời gian thực hiện trong trường hợp xấu nhất sẽ là O(n2).
Phân tích Flagged Bubble Sort trường hợp trung bình • Xác định thời gian chạy trung bình thì khó hơn, do ta không chắc chắn khi nào giải thuật kết thúc. • Ta cần một cách khác cho phép ta đếm được số các hoán đổi xảy ra. • Nếu trung bình các hoán đổi Θ(n2), thì thời gian chạy trung bình ít nhất phải là Ω (n2).
Flagged Bubble Sort trường hợp trung bình • 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
Flagged Bubble Sort trường hợp trung bình • Ví dụ, với hoán vị cho trước như sau: 3, 2, 0, 5, 4, 1 các nghịch thế là : (3, 2) (3, 0) (3, 1) (2, 0) (2, 1) (5, 4) (5, 1) (4, 1)
Flagged Bubble Sort trường hợp trung bình • Nếu phép hoán đổi hai phần tử kề nhau không có thứ tự, chính xác là ta đã xóa đi một nghịch thế. • Ví dụ, hoán đổi 5 và 4: (3, 2, 0, 5, 4, 1) (3, 2, 0, 4, 5, 1) chỉ có bớt đi một nghịch thế: (3, 2) (3, 0) (3, 1) (2, 0) (2, 1) (5, 4) (5, 1) (4, 1) • Bubble sort chỉ hoán đổi hai phần tử kề nhau mà thôi.
Flagged Bubble Sort trường hợp trung bình • Ví dụ, dãy chưa được sắp sau chứa 50 phần tử 261 548 3 923 195 973 289 237 57 299 594 928 515 55 507 351 262 797 788 442 97 798 227 127 474 825 7 182 929 852 504 485 45 98 538 476 175 374 523 800 19 901 349 947 613 265 844 811 636 859 có 522 cặp có thứ tự ngược và 703 cặp có thứ tự • Công thức cho ta là 612.5 nghịch thế