tailieunhanh - bài giảng các chuyên đề phần 4

Vậy thuật toán sắp xếp nổi bọt cũng có cấp là O(n2). Bất kể tình trạng dữ liệu vào như thế nào. IV. THUẬT TOÁN SẮP XẾP KIỂU CHÈN Xét dãy khoá k1, k2, ., kn. Ta thấy dãy con chỉ gồm mỗi một khoá là k1 có thể coi là đã sắp xếp rồi. Xét thêm k2, ta so sánh nó với k1, nếu thấy k2 | Cấu trúc dữ liệu và giải thuật 45 Vậy thuật toán sắp xếp nổi bọt cũng có cấp là O n2 . Bất kể tình trạng dữ liệu vào như thế nào. IV. THUẬT TOÁN SẮP XẾP KIỂU CHÈN Xét dãy khoá k1 k2 . kn. Ta thấy dãy con chỉ gồm mỗi một khoá là ki có thể coi là đã sắp xếp rồi. Xét thêm k2 ta so sánh nó với k1 nếu thấy k2 k1 thì chèn nó vào trước k1. Đối với k3 ta lại xét dãy chỉ gồm 2 khoá k1 k2 đã sắp xếp và tìm cách chèn k3 vào dãy khoá đó để được thứ tự sắp xếp. Một cách tổng quát ta sẽ sắp xếp dãy k1 k2 . ki trong điều kiện dãy k1 k2 . ki-1 đã sắp xếp rồi bằng cách chèn ki vào dãy đó tại vị trí đúng khi sắp xếp. procedure InsertionSort var i j Integer tmp TKey Biến giữ lại giá trị khoá chèn begin for i 2 to n do Chèn giá trị k vào dãy ki . ki-1 để toàn đoạn ki k2 . ki trở thành đã sắp xếp begin tmp ki Giữ lại giá trị k j i - 1 while j 0 and tmp kj do So sánh giá trị cần chèn với lần lượt các khoá k i-1 j 0 begin kj 1 kj Đẩy lùi giá trị k về phía sau một vị trí tạo ra khoảng trống tại vị trí j j j - 1 end kj 1 tmp Đưa giá trị chèn vào khoảng trống mới tạo ra end end Đối với thuật toán sắp xếp kiểu chèn thì chi phí thời gian thực hiện thuật toán phụ thuộc vào tình trạng dãy khoá ban đầu. Nếu coi phép toán tích cực ở đây là phép so sánh tmp kj thì Trường hợp tốt nhất ứng với dãy khoá đã sắp xếp rồi mỗi lượt chỉ cần 1 phép so sánh và như vậy tổng số phép so sánh được thực hiện là n - 1. Trường hợp tồi tệ nhất ứng với dãy khoá đã có thứ tự ngược với thứ tự cần sắp thì ở lượt thứ i cần có i - 1 phép so sánh và tổng số phép so sánh là n - 1 n - 2 . 1 n n - 1 2. Trường hợp các giá trị khoá xuất hiện một cách ngẫu nhiên ta có thể coi xác suất xuất hiện mỗi khoá là đồng khả năng thì có thể coi ở lượt thứ i thuật toán cần trung bình i 2 phép so sánh và tổng số phép so sánh là 1 2 2 2 . n 2 n 1 n 4. Nhìn về kết quả đánh giá ta có thể thấy rằng thuật toán sắp xếp kiểu chèn tỏ ra tốt hơn so với thuật toán sắp xếp chọn và sắp xếp nổi bọt. Tuy nhiên chi phí thời gian thực hiện của thuật toán .