Tin học 7 Cánh diều Bài 3: Sắp xếp chọn

- Ví dụ: Cần đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để tạo ra được dãy có thứ tự giảm dần.

- Minh họa ý tưởng:

 Minh họa ý tưởng sắp xếp bằng cách chọn dần

- Giải thích:

+ Bước 1. Số lớn nhất trong dãy số (94) cần được chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 94 và 55, dãy còn lại là: 19, 42, 55, 18, 67.

+ Bước 2. Số lớn nhất trong dãy là 67 chuyển về đầu dãy này, do đó đổi chỗ 67 với 19, dãy còn lại chưa được sắp xếp là 42, 55, 18, 19.

+ Tiếp tục lặp lại việc “Chọn số lớn nhất và đổi chỗ cho nói với số đứng đầu dãy”, cho đến khi hết dãy ban đầu.

- Minh họa:

+ Lượt 1. Xét a₁; Tìm số lớn nhất trong dãy a₁ đến a₆ rồi đổi chỗ với a₁.

+ Lượt 2. Xét a₂; Tìm số lớn nhất trong dãy a2 đến a₆ rồi đổi chỗ với a2.

+ Lượt 3. Xét a₃; Tìm số lớn nhất trong dãy a₃ đến a6 rồi đổi chỗ với a3.

+ Lượt 4. Xét a₄; Tìm số lớn nhất trong dãy a₄ đến a6 rồi đổi chỗ với a4.

+ Lượt 5. Xét a₅; Tìm số lớn nhất trong dãy a₅ đến a6 rồi đổi chỗ với a₅.

+ Lượt 6. Xét a₆; Đã xét xong dãy

→ Ta thu được dãy sắp xếp theo chiều giảm dần

Bài toán sắp xếp đặt ra như sau:

- Đầu vào: Dãy số a₁, a₂, …, a_n gọi là dãy (a).

- Đầu ra: Dãy số gồm các dãy số (a) những thứ tự giảm dần.

Thuật toán gồm một vòng lặp n – 1 lần, mỗi lần lặp nhằm đưa số của dãy vào đúng vị trí mong muốn.

Lặp với i từ 1 đến n – 1:

     a) Tìm số lớn nhất trong dãy số a_i, a_i+1, …, a_n gọi là a_m

     b) Đổi chỗ a_m và a_i cho nhau

Hết lặp

Trong các bước trên có yêu cầu tìm số lớn nhất trong dãy số cho trước (a).

Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào:

- Bước 1. Tạm ghi nhận vị trí của số lớn nhất là 1.

Minh họa cách tìm số lớn nhất trong dãy số

- Bước 2. So sánh a₂ với số lớn nhất, nếu a₂ lớn hơn số lớn nhất thì ghi nhận lại vị trị số lớn nhất là 2.

Cứ tiếp tục như vậy, đến khi so sánh xong a_n với số lớn nhất và ghi nhận lại vị trí của số lớn nhất thì số lớn nhất chính là số lớn nhất trong toàn bộ dãy và tìm được vị trí m của số lớn nhất trong dãy.

Sắp xếp là bài toán cơ sở trong tin học. Duy trì dữ liệu được sắp xếp đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu.

Khi phát biểu bài toán cần xác định rõ:

- Dãy đầu vào: Sắp xếp những gì?

- Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dần?

Ví dụ: Sắp xếp danh sách kết quả điểm kiểm tra môn Tin học theo thứ tự từ cao xuống thấp là bài toán sắp xếp. Tiêu chí là điểm kiểm tra theo thứ tự giảm dần.

Bài tập 1: Sắp xếp chọn dần là gì?

Hướng dẫn giải:

Sắp xếp chọn dần là: Chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó.

Bài tập 2: Trong bài toán sắp xếp giảm dần dãy số 11, 70, 20, 39, 80, 52, 41, 5. Ở bước đầu tiên của sắp xếp chọn ta cần đôi chỗ phần tử 80 cho phần tử nào?

Hướng dẫn giải:

Số lớn nhất trong dãy số (80) cần đươc chuyền về vị trí thứ nhất trong dãy, do đó đổi chỗ 80 với 11.

Bài tập 3: Khi phát biểu bài toán sắp xếp cần xác định rõ các yếu tố nào?

Hướng dẫn giải:

Khi phát biểu bài toán sắp xếp cần xác định rõ:

- Dãy đầu vào: Sắp xếp những gì?

- Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dân?

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

- Biết được bài toán sắp xếp là gì?

- Biết được ý tưởng sắp xếp chọn

- Mô phỏng được hoạt động của thuật toán sắp xếp chọn bằng các bước thủ công trên một bộ dữ liệu có kích thước nhỏ

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 Cánh diều Chủ đề F Bài 3 cực hay có đáp án và lời giải chi tiết. 

• Câu 1:

  Sắp xếp chọn dần là gì?

  • A. Chọn ra những phần tử chưa sắp xếp còn lại và xếp vào đầu dãy đó
  • B. Chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó
  • C. Chọn ra các phần tử dương
  • D. Chọn ra các phần tử âm

• Câu 2:

  Trong bài toán sắp xếp giảm dần dãy số 11, 70, 20, 39, 80, 52, 41, 5. Ở bước đầu tiên của sắp xếp chọn ta cần đổi chỗ phân tử 80 cho phần tử nào?

  • A. 11
  • B. 70
  • C. 5
  • D. 39

• Câu 3:

  Cho dãy số 2, 5, 4, 9, 3, 7. Sắp xếp dãy số theo thứ tự giảm dần theo cách chọn dần thì sau bước thứ nhất ta được dãy số nào?

  • A. 9, 5, 4, 2, 3, 7
  • B. 9, 7, 5, 4, 3, 2
  • C. 9, 5, 4, 2, 7, 3
  • D. 2, 5, 4, 9, 3, 7

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 Cánh diều Chủ đề F Bài 3 để 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 84 SGK Tin học 7 Cánh diều - CD

Hoạt động trang 85 SGK Tin học 7 Cánh diều - CD

Luyện tập trang 86 SGK Tin học 7 Cánh diều - CD

Vận dụng trang 86 SGK Tin học 7 Cánh diều - CD

Câu hỏi tự kiểm tra 1 trang 86 SGK Tin học 7 Cánh diều - CD

Câu hỏi tự kiểm tra 2 trang 86 SGK Tin học 7 Cánh diều - CD

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!