Please enable JavaScript.
Coggle requires JavaScript to display documents.
Bài 21: Các thuật toán sắp xếp đơn giản (Tin học 11 KNTT) - Coggle Diagram
Bài 21: Các thuật toán sắp xếp đơn giản (Tin học 11 KNTT)
Khái niệm và Mục đích
Sắp xếp (Sorting): Sắp xếp các phần tử trong một danh sách theo một thứ tự xác định
Mục đích: Giúp việc tìm kiếm và xử lý dữ liệu sau này trở nên hiệu quả hơn
Thuật toán Sắp xếp Chèn (Insertion Sort)
3) Ý tưởng chính: Xây dựng dãy đã sắp xếp từng bước một. Tại mỗi bước, lấy một phần tử từ dãy chưa sắp xếp và chèn nó vào đúng vị trí trong dãy con đã sắp xếp ở phía trước.
2) Mô phỏng/Thực hiện:
Duyệt từ phần tử thứ hai đến cuối dãy.
So sánh key với các phần tử trong dãy con đã sắp xếp và dịch chuyển các phần tử lớn hơn lên một vị trí.
Chèn key vào vị trí còn trống.
Giữ phần tử đang xét (key).
3) Đánh giá (Độ phức tạp):
Tốt nhất (Best case - dãy đã sắp xếp): O(n)
Trung bình/Tồi nhất (Average/Worst case): O(n^2)
Thuật toán Sắp xếp Chọn (Selection Sort)
1) Ý tưởng chính: Tại mỗi bước, tìm phần tử nhỏ nhất (hoặc lớn nhất) trong dãy chưa sắp xếp và đổi chỗ nó với phần tử ở vị trí đầu tiên của dãy chưa sắp xếp đó.
2) Mô phỏng/Thực hiện:
Duyệt từ vị trí đầu tiên đến gần cuối dãy.
Trong mỗi lần lặp, tìm chỉ số của phần tử nhỏ nhất trong phần còn lại của dãy.
Đổi chỗ phần tử nhỏ nhất tìm được với phần tử tại vị trí đang xét.
3) Đánh giá (Độ phức tạp): Mọi trường hợp (Best/Average/Worst case): O(n^2)
Thuật toán Sắp xếp Nổi bọt (Bubble Sort)
1) Ý tưởng chính: Lặp lại việc duyệt qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự. Các phần tử lớn hơn sẽ "nổi" dần lên cuối dãy sau mỗi lần duyệt.
2) Mô phỏng/Thực hiện:
Lặp lại việc duyệt dãy từ đầu đến cuối.
So sánh và hoán đổi cặp (a[j], a[j+1]) nếu chúng sai thứ tự.
Sau lần duyệt thứ $i$, $i$ phần tử cuối cùng đã ở đúng vị trí.
Có thể tối ưu bằng cách dừng sớm nếu không có sự hoán đổi nào xảy ra trong một lần duyệt.
3) Đánh giá (Độ phức tạp):
Tốt nhất (Best case - dãy đã sắp xếp): O(n)
Trung bình/Tồi nhất (Average/Worst case): O(n^2)
So sánh chung
Tính ổn định (Stable):
Chèn: Có
Chọn: Không
Nổi bọt: Có
Hiệu quả: Cả ba đều có độ phức tạp O(n^2) trong trường hợp xấu nhất, nên không hiệu quả với dữ liệu lớn.
