Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
là một thuật toán đơn giản, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự, cho đến khi toàn bộ dãy được sắp xếp.
Vì tìm kiếm nhị phân cần danh sách đã sắp xếp để biết chắc phần tử cần tìm nằm ở bên trái hay bên phải. Nếu không sắp xếp, ta không thể loại bỏ nửa danh sách một cách chính xác
đây nhé
Dãy ban đầu: [7.5, 9.0, 6.0, 8.5, 7.0]
- Lượt 1: so sánh dần, đổi chỗ → [7.5, 6.0, 8.5, 7.0, 9.0]
- Lượt 2: tiếp tục đổi chỗ → [6.0, 7.5, 7.0, 8.5, 9.0]
- Lượt 3: tiếp tục → [6.0, 7.0, 7.5, 8.5, 9.0]
- Lượt 4: dãy đã đúng thứ tự.
Kết quả: [6.0, 7.0, 7.5, 8.5, 9.0]
Đáp án : 1. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
Vòng lặp 1:
Dãy ban đầu: 3, 2, 4, 1, 5
Tìm số nhỏ nhất từ vị trí 0 đến 4 → là 1
Đổi chỗ 1 với 3
Kết quả sau vòng 1: 1, 2, 4, 3, 5
Vòng lặp 2:
Dãy hiện tại: 1, 2, 4, 3, 5
Tìm số nhỏ nhất từ vị trí 1 đến 4 → là 2
Đã đúng vị trí → không đổi
Kết quả sau vòng 2: 1, 2, 4, 3, 5
Vòng lặp 3:
Dãy hiện tại: 1, 2, 4, 3, 5
Tìm số nhỏ nhất từ vị trí 2 đến 4 → là 3
Đổi chỗ 3 với 4
Kết quả sau vòng 3: 1, 2, 3, 4, 5
Vòng lặp 4:
Dãy hiện tại: 1, 2, 3, 4, 5
Tìm số nhỏ nhất từ vị trí 3 đến 4 → là 4
Đã đúng vị trí → không đổi
Kết quả sau vòng 4: 1, 2, 3, 4, 5
Kết luận:
Dãy số sau khi sắp xếp tăng dần là: 1, 2, 3, 4, 5
Thuật toán tìm kiếm nhị phân được thực hiện trên một danh sách đã được (1) sắp xếp. Bắt đầu từ vị trí ở (2) giữa của danh sách. Tại mỗi bước, ta so sánh giá trị cần tìm với giá trị ở vị trí đó. Nếu giá trị cần tìm lớn hơn, ta tìm ở (3) nửa phải của danh sách. Nếu nhỏ hơn, ta tìm ở (4) nửa trái của danh sách.
Sự khác biệt cơ bản nhất là thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp, trong khi thuật toán tìm kiếm tuần tự không có yêu cầu này. Ngoài ra, cách thức tìm kiếm của thuật toán nhị phân là chia để trị, còn thuật toán tuần tự là duyệt lần lượt từng phần tử
Tìm kiếm tuần tự duyệt từng phần tử một, không cần sắp xếp. Tìm kiếm nhị phân chia đôi danh sách mỗi bước, cần sắp xếp trước.
Việc chia bài toán lớn thành những bài toán nhỏ giúp thuật toán sắp xếp dễ hiểu hơn, dễ thực hiện hơn và hiệu quả hơn. Khi giải quyết từng phần nhỏ, ta sắp xếp nhanh và chính xác, rồi ghép lại sẽ được kết quả đúng cho cả bài toán.