Lý thuyết Tin Học 7 Bài 14 (Chân trời sáng tạo): Thuật toán sắp xếp

Lý thuyết Tin Học 7 Bài 14: Thuật toán sắp xếp

1. Thuật toán sắp xếp nổi bọt

- Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử (tăng dần hay giảm dần) bằng cách thực hiện lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự.

- Mô tả thuật toán sắp xếp nổi bọt (áp dụng cho bài toán sắp xếp dãy tổng quát)

Đầu vào: Dãy chưa được sắp xếp.

Đầu ra: Dãy được sắp xếp không giảm.

1. Chuyển phần tử nhỏ nhất về vị trí đầu tiên.

+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên.

+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.

+ Kết thúc vòng lặp, phần từ nhỏ nhất "nổi lên" vị trí đầu tiên của dãy.

2. Chuyển phần tử nhỏ thứ hai về vị trí thứ hai.

+ So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai.

+ Nếu nhỏ hơn thì đổi chỗ hai phần tử.

+ Kết thúc vòng, phần tử nhỏ thứ hai "nổi lên" vị trí thứ hai của dãy.

4. Kết thúc thuật toán, ta sẽ nhận được dãy số đã được sắp xếp theo thứ tự tăng dần.

2. Thuật toán sắp xếp chọn

- Thuật toán sắp xếp chọn thực hiện lặp lại quá trình chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy đó.

Ví dụ:

Hình 2. Minh họa thuật toán sắp xếp nổi bọt