Tin học 7 Chân trời sáng tạo Bài 14: Thuật toán sắp xếp

* Bài toán:

Có 4 tấm thẻ, mỗi thẻ ghi một số và xếp thành một dãy dọc trên mặt bàn từ trên xuống dưới như Hình 1. Em hãy trao đổi với bạn để chỉ ra cách sắp xếp dãy thẻ theo thứ tự giá trị tăng dần của số ghi trên thẻ, với điều kiện chỉ có thể di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liền kề.

Các thẻ được ghi số và xếp theo dãy dọc

* 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.

Bước 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.

Bước 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.

Bước 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.

Bước 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ụ:

- Đầu vào: Dãy thẻ ghi các số xếp từ trái qua phải là 20, 21, 17, 19.

- Đầu ra: Dãy thẻ ghi các số được sắp xếp tăng dần là 17, 19, 20, 21.

Dãy số thẻ chưa sắp xếp

* Mô tả thuật toán:

Minh họa thuật toán sắp xếp nổi bọt

Bài tập 1: Bài toán: Em hãy thực hiện sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm. Với bài toán này em có thể sử dụng thuật toán sắp xếp nào?

Hướng dẫn giải:

Bài toán sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm có thể sử dụng thuật toán sắp xếp nổi bọt hoặc chọn.

Bài tập 2: Cho dãy số xếp từ trái qua phải là; 20, 21, 17, 19. Cho biết với thuật toán sắp xếp chọn thì kết quả sau vòng lặp 1 là bao nhiêu?

Hướng dẫn giải:

Kết quả sau vòng lặp 1. Dãy được sắp xếp là: 17, 21, 20, 19.

Bài tập 3: Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số không giảm bằng cách nào?

Hướng dẫn giải:

Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số không giảm bằng cách: Lặp lại quá trình chọn số nhỏ nhất trong dãy chưa sắp xếp và đưa số này về vị trí đầu tiên.

Qua bài học các em có thể:

- Giải thích được thuật toán sắp xếp nổi bọt, sắp xếp chọn.

- Biểu diễn và mô phỏng được thuật toán sắp xếp trên bộ dữ liệu đầu vào có kích thước nhỏ.

- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 14 cực hay có đáp án và lời giải chi tiết. 

• Câu 1:

  Chỉ ra phương án sai? Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là gì?

  • A. Giúp công việc đơn giản hơn
  • B. Giúp công việc dễ giải quyết hơn
  • C. Làm công việc trở nên phức tạp hơn
  • D. Giúp bài toán trở nên dễ hiểu hơn

• Câu 2:

  Đặc điểm của thuật toán sắp xếp nổi bọt là gì?

  • A. Lặp lại quá trình chọn phân tử nhỏ nhất đưa về vị trí đầu tiên
  • B. 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ự
  • C. Lặp đi lặp lại việc đổi chỗ 2 phân tử liền kề nhau
  • D. Lặp đi lặp lại việc đổi chỗ 2 phân tử đối xứng nhau

• Câu 3:

  Đặc điểm của thuật toán sắp xếp chọn là gì?

  • A. Lặp lại quá trình chọn phân tử nhỏ nhất (hoặc lớn 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 đó
  • B. 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ự
  • C. Lặp đi lặp lại việc đổi chỗ 2 phân tử liền kề nhau
  • D. Lặp đi lặp lại việc đổi chỗ 2 phân tử đôi xứng nhau

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 14 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 76 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 1 trang 79 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 2 trang 79 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 1 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST

Khám phá 2 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST

Luyện tập 1 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST

Luyện tập 2 trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST

Vận dụng trang 82 SGK Tin học 7 Chân trời sáng tạo - CTST

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!