Please enable JavaScript.
Coggle requires JavaScript to display documents.
CÁC THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP - Coggle Diagram
CÁC THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP
TÌM KIẾM
Thuật toán sắp xếp chèn (Insertion Sort)
VD: Sắp xếp tăng dần dãy [5, 1, 4, 2]: Chèn (1) vào [5] -> [1, 5]. Chèn (4) vào [1, 5] -> [1, 4, 5]. Chèn (2) vào [1, 4, 5] -> [1, 2, 4, 5].
Code:
Định nghĩa: Giả sử một phần đầu của mảng đã được sắp xếp. Ở mỗi bước, lấy phần tử tiếp theo từ đoạn chưa sắp xếp và chèn nó vào đúng vị trí trong đoạn đã sắp xếp.
Thuật toán nổi bọt (Bubble Sort)
VD: Sắp xếp tăng dần dãy [5, 1, 4, 2]: So sánh từng cặp (5, 1) -> hoán đổi, (5, 4) -> hoán đổi, (5, 2) -> hoán đổi, (5) nổi lên cuối. Lặp lại với phần còn lại đến khi nào hoàn toàn sắp xếp đc từ bé đến lớn
Định nghĩa: Lặp đi lặp lại việc so sánh và hoán đổi các cặp phần tử liền kề nếu chúng không theo thứ tự mong muốn, cho đến khi không còn cặp nào cần hoán đổi. Phần tử lớn nhất "nổi" lên cuối mảng sau mỗi lần lặp.
Code:
Thuật toán sắp xếp chọn (Selection Sort)
VD: Sắp xếp tăng dần dãy [5, 1, 4, 2]: Bước 1: Tìm min là (1), Hoán đổi 1 với 5 -> Dãy: [1, 5, 4, 2] -> Bước 2: Tìm min trong [5, 4, 2] là 2 -> Hoán đổi 2 với 5 -> Dãy: [1, 2, 4, 5].
Code:
Định nghĩa: Ở mỗi bước, tìm phần tử nhỏ nhất (hoặc lớn nhất) trong đoạn chưa sắp xếp còn lại và hoán đổi nó về vị trí đầu của đoạn chưa sắp xếp.
SẮP XẾP
Thuật toán tìm kiếm tuần tự (Linear Search)
VD: Để tìm số 8 trong dãy [4, 2, 8, 1, 6]: So sánh 8 với 4, 2, rồi đến 8 (Bằng, dừng lại).
Định nghĩa: Duyệt qua từng phần tử của danh sách/mảng cho đến khi tìm thấy giá trị mong muốn hoặc hết mảng. Phù hợp cho mảng chưa sắp xếp.
Code
Thuật toán tìm kiếm nhị phân (Binary Search)
VD: Để tìm số 25 trong dãy đã sắp xếp [10, 20, 25, 30, 40]: So sánh 25 với phần tử ở giữa (25) (Bằng, dừng lại)
Code:
Định nghĩa: Áp dụng cho mảng đã sắp xếp. So sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu không bằng, loại bỏ nửa mảng không chứa giá trị đó và tiếp tục lặp lại trên nửa còn lại.
TRƯỜNG + KHÁNH
