TAILIEUCHUNG - 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 .

• Cơ sở dữ liệu
• thuật toán tìm kiếm
• các chuyên đề thuật toán
• lập trình pascal
• lập trình các giải thuật
• Các thuật toán tìm kiếm
• Tìm kiếm trên đồ thị
• Bài toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều rộng
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Tìm kiếm dựa trên quy hoạch động
• Tìm kiếm dựa trên đệ quy
• Tìm kiếm dựa trên phân vùng
• Khái niệm tìm kiếm
• Bài toán tìm kiếm
• Tìm kiếm trên dãy chưa sắp
• Cấu trúc dữ liệu
• Kỹ thuật tìm kiếm
• Tìm kiếm trên mảng
• Giải thuật tìm kiếm
• Tìm kiếm trên tập tin
• Tìm kiến tuyến tính
• Thuật toán tìm kiếm tối ưu
• Tìm kiếm cứu nạn
• Thuật toán vi khuẩn
• Tính toán phương án tìm kiếm tối ưu
• Tàu tìm kiếm cứu nạn
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Ứng dụng thuật toán tìm kiếm đồ thị
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Khái niệm về tìm kiếm
• Phương pháp tìm kiếm tuần tự
• Phương pháp tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân cơ bản
• Thuật toán Quicksort
• Cách tìm kiếm nhị phân
• chiến lược tìm kiếm mù
• Tìm kiếm beam
• Tìm kiếm leo đồi
• tìm kiếm tối ưu
• Tìm kiếm có đối thủ
• Tìm kiếm mô phỏng sự tiến hóa
• Thuật toán di truyền
• Bài toán giải thuật
• Chiến lược tìm kiếm
• Tìm kiếm trình tự
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán sắp xếp
• Thuật toán tìm kiếm tuần tự
• Thuật toán sắp xếp nổi bọt
• khoa học
• tự nhiên
• toán học
• Các thuật toán tìm kiếm trên đồ thị
• Các giải thuật tìm kiếm
• Giải thuật tìm kiếm tuyến tính
• Giải thuật Tìm kiếm nhị phân
• Các giải thuật sắp xếp
• Tóm tắt Luận án Thạc sĩ
• Hệ thống thông tin
• Tìm kiếm chuỗi DNA
• Tìm kiếm tương tự nhanh
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Bài giảng Cấu trúc dữ liệu
• Tìm kiếm trên danh sách
• Tìm kiếm trên văn bản
• Bài giảng Tìm kiếm
• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Thuật giải HEURISTIC
• phương pháp tìm kiếm HEURISTIC
• thuật toán tìm kiếm leo đồi
• tìm kiếm ưu tiên tối ưu
• ứng dụng giải bài toán ta canh
• chiến lược tìm kiếm lai
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Cấu trúc dữ liệu trừu tượng
• Cài đặt tìm kiếm ở thư viện
• tài liệu học đại học
• bài giảng quy hoạch tuyến tính
• Khoa học máy tính
• tìm kiếm tuyến tính
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
• Ứng dụng các thuật toán
• Bài giảng Tìm kiếm đối kháng
• Tìm kiếm đối kháng
• Tìm kiếm đối kháng trò chơi
• Thuật toán MINIMAX
• Hàm lượng giá
• Tìm kiếm cắt nhánh