tailieunhanh - Thuật toán BubbleSort

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ộ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 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à: 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) . . | 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, .