Lý thuyết Tin học 7 Chân trời sáng tạo Bài 14: Thuật toán sắp xếp
Haylamdo biên soạn và sưu tầm tóm tắt lý thuyết Tin học lớp 7 Bài 14: Thuật toán sắp xếp sách Chân trời sáng tạo hay nhất, ngắn gọn sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học 7.
Lý thuyết Tin học 7 Chân trời sáng tạo Bài 14: Thuật toán sắp xếp
Chỉ từ 100k mua trọn bộ lý thuyết Tin 7 Chân trời sáng tạo (cả năm) bản word trình bày đẹp mắt, dễ dàng chỉnh sửa:
- B1: gửi phí vào tk:
0711000255837- NGUYEN THANH TUYEN - Ngân hàng Vietcombank (QR) - B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án
1. Thuật toán sắp xếp nổi bọt
- Thuật toán thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.
- Mô tả thuật toán sắp xếp nổi bọ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.
1.1. So sánh từng phần tử trong 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.
1.2. Nếu nhỏ hơn thì đổi chỗ cho 2 phần tử.
1.3. 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.
2.1. So sánh từng phần tử trong 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.
2.2. Nếu nhỏ hơn thì đổi chỗ cho 2 phần tử.
2.3. Kết thúc vòng lặp, phần tử nhỏ thứ hai nổi lên vị trí thứ hai của dãy.
3. Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư, … cho đến phần tử liền trước phần tử cuối cùng.
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.
Ví dụ: Sắp xếp tăng dần các thẻ số sau:
Hình 1. Các thẻ số được sắp xếp theo dãy dọc.
- Mô phỏng thuật toán sắp xếp nổi bọt.
+ Đầu vào: Dãy thẻ ghi các số xếp từ trên xuống dưới: 19, 16, 18, 15.
+ Đầu ra: Dãy thẻ ghi các số được sắp xếp tăng dần: 15, 16, 18, 19.
Hình 2. Vòng lặp 1 của thuật toán sắp xếp nổi bọt.
Hình 3. Vòng lặp 2 của thuật toán sắp xếp nổi bọt.
Hình 4. Vòng lặp 3 của thuật toán sắp xếp nổi bọt.
- Ở mỗi vòng lặp, ta di chuyển được một số về đúng thứ tự của nó trong dãy số. Khi thực hiện thuật toán, các số nhỏ di chuyển dần lên trên, giống như bọt khí nhẹ nổi lên mặt nước, nên gọi là thuật toán sắp xếp nổi bọt.
2. Thuật toán sắp xếp chọn
- Thuật toán thực hiện việc chọn số nhỏ nhất trong dãy chưa được sắp xếp và đưa số này về vị trí đầu tiên của dãy chưa được sắp xếp. Lặp lại quá trình này cho đến khi dãy chưa sắp xếp chỉ còn một phần tử.
Ví dụ: Sắp xếp các thẻ có giá trị tăng dần.
Hình 5. Dãy thẻ số chưa được sắp xếp.
- Mô phỏng thuật toán sắp xếp chọn:
Hình 6. Vòng lặp 1 của thuật toán sắp xếp chọn.
Hình 7. Vòng lặp 2 của thuật toán sắp xếp chọn.
Hình 8. Vòng lặp 3 của thuật toán sắp xếp chọn.
Hình 9. Dãy được sắp xếp xong.
- Ở mỗi vòng lặp, ta di chuyển được một số về đúng thứ tự của nó trong dãy số.
- Với thuật toán sắp xếp chọn, bài toán sắp xếp dãy số ban đầu cũng được chia thành những bài toán nhỏ để giải quyết. Cụ thể, các bài toán nhỏ là di chuyển số nhỏ nhất về vị trí đầu tiên của dãy chưa sắp xếp. Trong đó, phạm vi của dãy chưa sắp xếp giảm dần sau mỗi lần lặp.