Sách Giáo Khoa 247

Tin Học 7 - BÀI 16: THUẬT TOÁN SẮP XẾP | Kết Nối Tri Thức Với Cuộc Sống

Xem chi tiết nội dung bài BÀI 16: THUẬT TOÁN SẮP XẾP và tải xuống miễn phí trọn bộ file PDF Sách Tin Học 7 | Kết Nối Tri Thức Với Cuộc Sống

Trang 78

Sau bài học này em sẽ:

  • Giải thích được một vài thuật toán sắp xếp cơ bản.

  • Biểu diễn và mô phỏng được hoạt động của thuật toán sắp xếp với 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ó hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16.1c, Hình 16.1d để biết cách thực hiện.

Hình 16.1. Hoán đổi

1. THUẬT TOÁN SẮP XẾP NỔI BỌT

Trong bài học trước, chúng ta đã biết sắp xếp giúp cho việc tìm kiếm được thực hiện dễ dàng. Trong cuộc sống hằng ngày, chúng ta thường xuyên phải thực việc sắp xếp các đồ vật đề dễ tìm. Máy tính cũng thường xuyên phải thực hiện thuật toán sắp xếp khi người sử dụng yêu cầu. Ví dụ: Sắp xếp điểm trung bình của học sinh trong lớp bằng phần mềm bảng tính; Sắp xếp tên tệp trong thư mục,... Có nhiều thuật toán sắp xếp khác nhau. Một trong số đó là thuật toán sắp xếp nổi bọt.

Giả sử ta cần phải sắp xếp dãy các số 4, 2, 3, 1 để thu được dãy có thứ tự tăng dần. Thuật toán sắp xếp nổi bọt xét từng vị trí từ đầu đến cuối dãy. Tại mỗi vị trí được xét, thuật toán tìm phần tử nhỏ nhất trong những phần tử phía sau đề đưa vào vị trí đó. Việc này được thực hiện bằng một vòng lặp, so sánh từng cặp phần tử cạnh nhau và hoán đổi chúng nếu số ở phía sau nhỏ hơn. Các bước thực hiện được mô tả trong Hình 16.2, Hình 16.3, Hình 16.4. Việc hoán đổi được thực hiện giống như việc hoán đổi ở Hoạt động khởi động.

Trang 79

4 2 3 1

Đầu vào

Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:

1 < 3 ⇒ hoán đổi

1 < 2 ⇒ hoán đổi

1 < 4 ⇒ hoán đổi

Kết thúc vòng lặp thứ nhất, số nhỏ nhất "nổi" lên vị trí đầu tiên

Hình 16.2. Vòng lặp thứ nhất của thuật toán nổi bọt

Xét vị trí thứ hai:

3 > 2 ⇒ KHÔNG hoán đổi

2 > 4 ⇒ KHÔNG hoán đổi

Kết thúc vòng lặp thứ hai, phần từ nhỏ thứ nhì "nổi" lên vị trí thứ hai

Hình 16.3. Vòng lặp thứ hai của thuật toán nổi bọt

Xét vị trí thứ ba:

3 < 4 ⇒ hoán đổi

Kết thúc vòng lặp thứ ba

Đầu ra

Hình 16.4. Vòng lặp thứ ba của thuật toán nổi bọt

Trang 80

Sau vòng lặp thứ ba, không có bất kì sự hoán đổi nào được thực hiện nữa nên thuật toán dừng lại. Danh sách được sắp xếp theo đúng thứ tự yêu cầu.

Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên:

Sắp xếp dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt.

1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:

1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.

1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đồi chỗ chúng cho nhau.

1.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên.

2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.

2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.

2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.

2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ ba, thứ tư,... đến vị trí trước vị trí cuối cùng.

4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Hoạt động 1: Mô phỏng thuật toán sắp xếp nổi bọt

Em hãy thực hiện thuật toán sắp xếp nổi bọt để sắp xếp 5 số sau đây theo thứ tự tăng dần. Hãy mô phỏng các bước lặp sắp xếp bằng hình vẽ minh họa tương tự như Hình 16.2, Hình 16.3, Hình 16.4.

3 5 4 1 2

Sắp xếp nổi bọt

Nổi bọt là thuật toán sắp xếp được thực hiện bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách:

A. Chọn phần tử có giá trị nhỏ nhất đưa vào đầu danh sách.

B. Chọn phần tử có giá trị lớn nhất đưa vào đầu danh sách.

C. Hoán đổi các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách sắp xếp theo đúng thứ tự.

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

Một thuật toán sắp xếp khác có tên là sắp xếp chọn. Thuật toán sắp xếp chọn xét từng phần tử của danh sách và chọn phần tử nhỏ nhất trong các phần tử chưa được sắp xếp. Phần tử nhỏ nhất được đưa vào vị trí đầu tiên của danh sách đã sắp xếp. Các bước được lặp lại cho đến khi toàn bộ danh sách được sắp xếp. Các bước của thuật toán sắp xếp chọn được mô tả bằng hình vẽ trong Hình 16.5.

Trang 81

Vòng lặp thứ nhất

Xét vị trí đầu tiên, lần lượt so sánh phần tử tại vị trí đó với các phần tử còn lại phía sau.

Nếu gặp phần tử nhỏ hơn thì hoán đổi phần tử này với phần tử tại vị trí đầu tiên của dãy.

Kết thúc vòng lặp thứ nhất, phần tử nhỏ nhất được đưa về vị trí đầu tiên.

 

 

 

KHÔNG hoán đổi

 1 < 3 → Hoán đổi

 KHÔNG hoán đổi

KHÔNG hoán đổi

Kết quả vòng lặp thứ nhất

Vòng lặp thứ hai được thực hiện tương tự như vòng lặp trước với vị trí thứ hai.

Kết quả vòng lặp thứ hai

Vòng lặp thứ ba được thực hiện tương tự như hai vòng lặp trước với vị trí thứ ba.

Kết quả vòng lặp thứ ba

Vòng lặp thứ tư được thực hiện tương tự như những vòng lặp trước với vị trí thứ tư.

Kết quả vòng lặp thứ tư

Đầu ra: Dãy các phần tử đã được sắp xếp

Hình 16.5. Mô phỏng thuật toán sắp xếp chọn

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên:

Sắp xếp dãy số theo thứ tự từ nhỏ đến lớn bằng thuật toán sắp xếp chọn.

1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:

1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên.

1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên.

1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.

2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.

2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai.

2.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đồi nó với phần tử tại vị trí thứ hai.

2.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ thứ nhì được đưa về vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ ba, thứ tư,... đến vị trí trước vị trí cuối cùng.

4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Trang 82

Hoạt động 2: Sắp xếp chọn

Chọn năm học sinh, mỗi học sinh viết ra tờ giấy một con số mà mình yêu thích. Các em đứng thành một hàng ngang và cầm tờ giấy có ghi con số để cả lớp có thể quan sát được.

Ví dụ:

41 15 17 32 18

Học sinh thử thực hiện thuật toán sắp xếp để sắp xếp các con số của năm bạn theo thứ tự tăng dần.

Thuật toán sắp xếp chọn xét từng vị trí từ đầu đến cuối dãy. So sánh trực tiếp phần tử vị trí đó được xét với những phần tử ở phía sau nó và hoán đổi nếu chúng chưa đúng thứ tự.

? Em hãy viết vào vở cụ thể các bước của vòng lặp thứ 2, 3, 4 được mô tả trong Hình 16.5.

3. CHIA BÀI TOÁN THÀNH NHỮNG BÀI TOÁN NHỎ HƠN

Trong quá trình thực hiện cả hai thuật toán sắp xếp nổi bọt và sắp xếp chọn, ta đều thấy xuất hiện nhiều lần thuật toán đơn giản hơn: hoán đổi giá trị hai phần tử. Như vậy, bài toán sắp xếp đã được giải quyết dựa trên lời giải của bài toán nhỏ hơn là bài toán hoán đồi giá trị.

Xem xét thuật toán tìm kiếm nhị phân ở bài học trước, ta cũng nhận thấy thuật toán tìm kiếm nhị phân thực hiện chia bài toán thành những bài toán nhỏ hơn. Trong đó, bài toán nhỏ hơn là một phần của bài toán ban đầu. Cụ thể, ở mỗi lần lặp, thuật toán tìm kiếm nhị phân đã thu hẹp vùng tìm kiếm chỉ còn một nửa.

Một cách khái quát, để giải quyết một bài toán, chúng ta đã dựa trên lời giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán nhỏ hơn giúp việc giải bài toán đó dễ dàng hơn, đồng thời việc mô tả thuật toán dễ hiểu và dễ thực hiện hơn.

Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?

A. Để thay đổi đầu vào của bài toán.

B. Để thay đổi yêu cầu đầu ra của bài toán.

C. Để bài toán dễ giải quyết hơn.

D. Để bài toán khó giải quyết hơn.

LUYỆN TẬP

  1. Em hãy liệt kê các bước lặp của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

  2. Em hãy liệt kê các bước lặp của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

VẬN DỤNG

Em hãy liên kết quá trình học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp chọn để sắp xếp các bạn trong tổ theo thứ tự tăng dần của điểm học tập. Trình bày cụ thể các bước của thuật toán sắp xếp chọn tương ứng với từng kết quả sắp xếp.

Xem và tải xuống trọn bộ sách giáo khoa Tin Học 7

Tổng số đánh giá:

Xếp hạng: / 5 sao

Sách giáo khoa liên quan

Toán 7 - Tập 1

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Toán 7 - Tập 2

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Ngữ Văn 7 - Tập 1

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Ngữ Văn 7 - Tập 2

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Tiếng Anh 7 - Tập 1

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Tiếng Anh 7 - Tập 2

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Vật Lí 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Sinh Học 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Lịch Sử 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Địa Lí 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Công Nghệ 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Âm Nhạc và Mĩ thuật 7

Sách Giáo Khoa Lớp 7 NXB Giáo Dục

Gợi ý cho bạn

my-thuat-thiet-ke-do-hoa-1178

Mỹ Thuật Thiết Kế Đồ Hoạ

Mỹ Thuật Thiết Kế Đồ Hoạ 11

cong-nghe-7-870

Công Nghệ 7

Sách Lớp 7 Cánh Diều

giao-duc-cong-dan-8-832

Giáo Dục Công Dân 8

Sách Lớp 8 NXB Giáo Dục Việt Nam

toan-9-tap-1-962

Toán 9 - Tập 1

Sách Lớp 9 Chân Trời Sáng Tạo

giao-duc-kinh-te-va-phap-luat-11-1190

Giáo dục Kinh tế và Pháp luật 11

Mỗi hoạt động trong sách đều được chỉ dẫn bằng số hiệu

Nhà xuất bản

canh-dieu-1

Cánh Diều

Bộ sách giáo khoa của Nhà xuất bản Cánh Diều

chan-troi-sang-tao-2

Chân Trời Sáng Tạo

Bộ sách giáo khoa của Nhà xuất bản Chân Trời Sáng Tạo

ket-noi-tri-thuc-voi-cuoc-song-3

Kết Nối Tri Thức Với Cuộc Sống

Sách giáo khoa của nhà xuất bản Kết Nối Tri Thức Với Cuộc Sống

giao-duc-viet-nam-5

Giáo Dục Việt Nam

Bộ Sách Giáo Khoa của Nhà Xuất Bản Giáo Dục Việt Nam

sach-bai-giai-6

Sách Bài Giải

Bài giải cho các sách giáo khoa, sách bài tập

sach-bai-tap-7

Sách Bài Tập

Sách bài tập tất cả các khối lớp

tai-lieu-hoc-tap-9

Tài liệu học tập

Đây là tài liệu tham khảo hỗ trợ trong quá trình học tập

global-success-bo-giao-duc-dao-tao-11

Global Success & Bộ Giáo Dục - Đào Tạo

Bộ sách Global Success & Bộ Giáo Dục - Đào Tạo là sự kết hợp giữa ngôn ngữ Tiếng Anh theo lối giảng dạy truyền thống và cập nhật những phương thức quốc tế

nxb-dai-hoc-su-pham-tphcm-12

NXB - Đại Học Sư Phạm TPHCM

NXB - Đại Học Sư Phạm TPHCM

Chủ đề

Liên Kết Chia Sẻ

mu88 ** Đây là liên kết chia sẻ bới cộng đồng người dùng, chúng tôi không chịu trách nhiệm gì về nội dung của các thông tin này. Nếu có liên kết nào không phù hợp xin hãy báo cho admin.