CHỦ ĐỀ 5: BÀI 16: THUẬT TOÁN SẮP XẾP
Trang bìa
Trang bìa
Ảnh
TIN HỌC 7
CHỦ ĐỀ 5: BÀI 16: THUẬT TOÁN SẮP XẾP
Ảnh
Mục tiêu bài học
Mục tiêu bài học
Hình vẽ
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.
Ảnh
Học xong bài này, em sẽ:
Khởi động
Khởi động
Khởi động
Có hai chất lỏng màu xanh và màu đỏ, chứa lần lượt trong chiếc cốc A và B (Hình 16.1a). Đổi chỗ hai chất lỏng, cốc A chứa chất lỏng màu đỏ, còn cốc B là màu xanh. Để thực hiện ta sử dụng thêm chiếc cốc thứ ba (cốc C). Quan sát Hình 16.1b, 16.1c, 16.1d để biết cách thực hiện.
Ảnh
1. Thuật toán sắp xếp nổi bọt
1. Kiến thức mới
Ảnh
1. Kiến thức mới
Hình vẽ
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. Thuật toán sắp xếp nổi bọt xét từng vị trí từ đầu tới 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í đó.
a. Tìm hiểu
b. Ví dụ minh họa
Hình vẽ
b. Ví dụ minh họa
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. Đầu vào: Dãy các phần tử chưa được sắp xếp.
Ảnh
Ảnh
- Vòng lặp thứ nhất của thuật toán nổi bọt (Các bước thực hiện mô tả thuật toán sắp xếp nổi bọt)
Ảnh
Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
Hình 16.2. Vòng lặp thứ nhất của thuật toán nổi bọt
- Vòng lặp thứ hai của thuật toán nổi bọt (Các bước thực hiện mô tả thuật toán sắp xếp nổi bọt)
Xét vị trí thứ hai:
Ảnh
Hình 16.3. Vòng lặp thứ hai của thuật toán nổi bọt
- Vòng lặp thứ ba của thuật toán nổi bọt (Các bước thực hiện mô tả thuật toán sắp xếp nổi bọt)
Xét vị trí thứ 3:
Hình 16.4. Vòng lặp thứ 3 của thuật toán nổi bọt
Ảnh
c. Mô tả thuật toán sắp xếp nooit bọt bằng ngôn ngữ tự nhiên:
Hình vẽ
c. 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ố bằng thuật toán sắp xếp nổi bọt.
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. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. Cuối vòng lặp em xẽ nhận được dãy số với phần từ nhỏ nhất nổi lên ở vị trí đầu tiên.
1. Vị trí thứ nhất:
Ảnh
- Ý 2 ( b. Mô tả thuật toán sắp xếp nooit bọt bằng ngôn ngữ tự nhiên:)
Hình vẽ
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. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. 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ứ 2.
2. Vị trí thứ hai:
Ảnh
- Ý 3 và ý 4 ( b. Mô tả thuật toán sắp xếp nooit bọt bằng ngôn ngữ tự nhiên:)
Hình vẽ
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.
Ảnh
2. Hoạt động 1: Mô phỏng thuật toán sắp xếp nổi bọt
2. Hoạt động 1: Mô phỏng thuật toán sắp xếp nổi bọt
Hình vẽ
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, 16.3, 16.4.
Ảnh
Ảnh
3. Kết luận
3. Kết luận
Ảnh
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ự.
4. Câu hỏi
4. Câu hỏi
Bài tập trắc nghiệm
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ị bé nhất đặt vào đầu danh sách.
B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách.
C. 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ự.
D. Chèn phần tử vào vị trí thích hợp để dả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
1. Kiến thức mới
1. Kiến thức mới
Ảnh
Hình vẽ
a. Tìm hiểu
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 vị trí và đưa từ phần tử nhỏ nhất trong những phần tử phía sau vào vị trí đó.
b. Ví dụ minh họa
Hình vẽ
b. Ví dụ minh họa
Giả sử ta cần phải sắp xếp dãy các số 3, 4, 1, 5, 2 để thu được dãy có thứ tự tăng dần. Đầu vào: Dãy các phần tử chưa được sắp xếp.
Ảnh
Ảnh
- Vòng lặp thứ nhất (Cấc bước mô phỏng thuật toán sắp xếp chọn)
- Vòng lặp thứ nhất:
Ảnh
- Vòng lặp thứ hai, ba, bốn (Cấc bước mô phỏng thuật toán sắp xếp chọn)
Ảnh
Ảnh
Ảnh
Vòng lặp thứ hai thực hiện tương tự như vòng lặp trước với vị trí thứ hai.
Vòng lặp thứ ba thực hiện tương tự như vòng lặp trước với vị trí thứ ba.
Vòng lặp thứ tư thực hiện tương tự như vòng lặp trước với vị trí thứ tư.
c. Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên
c. Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên
Hình vẽ
Sắp xếp dãy số bằng thuật toán sắp xếp chọn.
So sánh từng phần tử với phần tử tại vị trí đầu tiên. 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. 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.
1. Vị trí thứ nhất:
Ảnh
- Ý 2
Hình vẽ
So sánh hai phần tử với vị trí thứ hai. 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. Cuối vòng lặp, em sẽ nhận được dãy số nhỏ hơn hơn phần tử thứ nhì được đưa về vị trí thứ hai.
2. Vị trí thứ hai:
Ảnh
- Ý 3 và ý 4
Hình vẽ
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.
Ảnh
2. Hoạt động 2: Sắp xếp chọn
Hình vẽ
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 quan sát .
Ảnh
2. Hoạt động 2: Sắp xếp chọn
Học sinh thứ sáu thực hiện thuật toán sắp xếp chọn để sắp xếp các con số của năm bạn theo thứ tự tăng dần.
Ảnh
3. Kết luận
3. Kết luận
Ảnh
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ự
4. Câu hỏi
4. Câu hỏi
Ảnh
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
1. Kiến thức mới
1. Kiến thức mới
Hình vẽ
Trong quá trình thực hiện thuật toán sắp xếp nổi bọt và sắp xếp chọn , ta thấy xuất hiện nhiều thuật toán đơn giản hơn: hoán đổi giá trị hai phần 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ỏ giúp việc giải bài toán đó dễ dàng hơn đồng thời mô tả thuật toán dễ hiểu và dễ thực hiện hơn.
Ảnh
2. Kết luận
2. Kết luận
Ảnh
Chia một bài toán thành những bài toán nhỏ hơn giúp thuật toán dễ hiểu và dễ thực hiện hơn.
3. Câu hỏi
3. Câu hỏi
Bài tập trắc nghiệm
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.
4. Luyện tập
1. Câu 1
Ảnh
1. Câu 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. Câu 2
2. Câu 2
Ảnh
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.
5. Vận dụng
Vận dụng
Ảnh
Vận dụng
Em hãy ghi lại kết quả điểm 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 hoặc sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó.
Dặn dò
1. Dặn dò
Ảnh
Dặn dò
Ôn lại bài vừa học. Làm bài tập trong SBT.
2. Kết bài
Ảnh
Ảnh
Ảnh