Ôn tập lại các thuật toán tìm kiếm nhị phân, Tìm kiếm tuần tự ,sắp xếp nổi bọt

Ôn tập các thuật toán tìm kiếm và sắp xếp

1. Thuật toán tìm kiếm nhị phân

Mô tả:

Thuật toán tìm kiếm nhị phân là một thuật toán hiệu quả để tìm kiếm một phần tử trong một danh sách đã được sắp xếp theo thứ tự. Thuật toán này hoạt động bằng cách liên tục chia đôi danh sách và loại bỏ một nửa không thể chứa phần tử đang tìm kiếm.

Cách thực hiện:

1. Bắt đầu với hai chỉ số đầu và cuối của danh sách.
2. So sánh phần tử cần tìm với phần tử ở giữa danh sách.
3. Nếu phần tử cần tìm nhỏ hơn phần tử ở giữa, loại bỏ nửa bên phải của danh sách.
4. Nếu phần tử cần tìm lớn hơn phần tử ở giữa, loại bỏ nửa bên trái của danh sách.
5. Lặp lại các bước 2-4 cho đến khi tìm thấy phần tử cần tìm hoặc danh sách rỗng.

Ưu điểm:

• Hiệu quả cao, đặc biệt là với danh sách lớn.
• Chỉ cần thực hiện log2(n) phép so sánh, với n là số phần tử trong danh sách.

Nhược điểm:

• Danh sách cần được sắp xếp theo thứ tự.

Ví dụ:

Tìm kiếm phần tử 15 trong danh sách [1, 3, 5, 7, 9, 11, 13, 15, 17, 19].

• Bước 1: So sánh 15 với 11 (phần tử ở giữa danh sách).
• Bước 2: 15 > 11, loại bỏ nửa bên trái của danh sách.
• Bước 3: So sánh 15 với 15 (phần tử ở giữa danh sách).
• Bước 4: 15 = 15, tìm thấy phần tử cần tìm.

2. Thuật toán tìm kiếm tuần tự

Mô tả:

Thuật toán tìm kiếm tuần tự là một thuật toán đơn giản để tìm kiếm một phần tử trong một danh sách. Thuật toán này hoạt động bằng cách duyệt qua từng phần tử trong danh sách và so sánh nó với phần tử cần tìm.

Cách thực hiện:

1. Bắt đầu từ phần tử đầu tiên của danh sách.
2. So sánh phần tử cần tìm với phần tử hiện tại.
3. Nếu phần tử cần tìm bằng phần tử hiện tại, trả về vị trí của phần tử hiện tại.
4. Nếu phần tử cần tìm không bằng phần tử hiện tại, di chuyển đến phần tử tiếp theo.
5. Lặp lại các bước 2-4 cho đến khi tìm thấy phần tử cần tìm hoặc đến cuối danh sách.

Ưu điểm:

• Đơn giản và dễ hiểu.
• Không yêu cầu danh sách được sắp xếp.

Nhược điểm:

• Hiệu quả thấp với danh sách lớn.

Ví dụ:

Tìm kiếm phần tử 15 trong danh sách [1, 3, 5, 7, 9, 11, 13, 15, 17, 19].