THCS Tin học 7 – Thuật toán tìm kiếm & sắp xếp

Thuật toán là gì?

• Một chương trình máy tính

• Một dãy các lệnh lập trình

• Dãy các bước thực hiện theo tuần tự để giải quyết vấn đề

• Một loại phần mềm đặc biệt

Thuật toán tìm kiếm tuần tự thường áp dụng khi:

• Dãy đã được sắp xếp

• Dãy chưa được sắp xếp

• Dãy có ít phần tử

• Không cần kiểm tra từng phần tử

Thuật toán tìm kiếm nhị phân chỉ hoạt động hiệu quả khi:

• Dãy ngắn

• Dãy không sắp xếp

• Dãy đã sắp xếp

• Dãy chứa ký tự đặc biệt

Trong tìm kiếm tuần tự, phần tử cần tìm được so sánh bắt đầu từ:

• Cuối dãy

• Giữa dãy

• Bất kỳ vị trí nào

• Đầu dãy

Trong sắp xếp chọn, bước chính là:

• Chọn phần tử nhỏ nhất để đưa về cuối

• So sánh ngẫu nhiên hai phần tử

• Chọn phần tử lớn nhất trong dãy chưa sắp xếp

• Lặp lại cho đến khi dãy đảo ngược

Thuật toán sắp xếp nổi bọt hoạt động dựa trên nguyên tắc:

• Tìm kiếm phần tử giữa

• Đếm số lần xuất hiện

• So sánh và đổi chỗ các cặp liền kề

• Nhân bản dãy dữ liệu

Sắp xếp nổi bọt có thể sắp xếp:

• Chỉ tăng dần

• Chỉ giảm dần

• Cả tăng và giảm

• Không sắp xếp được

Trong tìm kiếm nhị phân, nếu phần tử giữa lớn hơn giá trị cần tìm:

• Chuyển sang bên phải

• Kết thúc thuật toán

• Chuyển sang bên trái

• Trả về phần tử giữa

Đặc điểm của sắp xếp chọn là:

• Sắp xếp theo từng lượt dựa vào phần tử đầu

• So sánh tất cả cặp liền kề

• Chọn phần tử thích hợp để đổi chỗ với phần tử đầu trong dãy chưa sắp xếp

• Không thay đổi vị trí các phần tử

Tại sao sắp xếp nổi bọt gọi là “nổi bọt”?

• Vì các phần tử nổi lên như bong bóng

• Vì phần tử lớn nhất "nổi" về cuối sau mỗi lượt

• Vì có dùng nước để sắp xếp

• Vì phần tử nhỏ được giữ lại