Hãy trình bày thuật toán sắp xếp nổi bọt theo phương pháp làm mịn dần

Sách bài tập Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình - Kết nối tri thức

Câu 26.7 trang 79 SBT Tin học 11: Hãy trình bày thuật toán sắp xếp nổi bọt theo phương pháp làm mịn dần.

Lời giải:

Một cách trình bày theo phương pháp làm mịn dần có thể như sau:

Bài toán: Cho trước dãy A có n phần tử. Cần sắp xếp dãy A theo thứ tự tăng dần theo thuật toán nổi bọt.

Bước 1. Phân tích và ý tưởng thiết kế ban đầu.

Ý tưởng chính của thuật toán sắp xếp chèn là liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng được sắp xếp không đúng, ví dụ nếu A[i] > A[i + 1] thì cần đổi chỗ hai phần tử này. Như vậy có thể thiết kế một ý tưởng như sau:

1 Lặp cho đến khi dãy ban đầu đã được sắp xếp đúng

2 Duyệt 1 lượt phần tử từ trái sang phải nếu 2 phần tử cạnh nhau sắp xếp không đúng chỗ thì đổi chỗ 2 phần tử này. 

Bước 2. Chi tiết hoá công việc mô tả trong dòng lệnh 2 ở trên.

Ý tưởng ban đầu là cần duyệt phần tử từ thứ nhất đến phần tử gần cuối cùng, kiểm tra phần tử đang duyệt và phần tử sau đó, nếu sắp xếp không đúng thì đổi chỗ. Vậy có thể hình dung dòng lệnh 2 ở trên được thể hiện như sau: for j in range(n-1): # n là số phần tử của dãy.

nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]

Quan sát kĩ hơn chúng ta thấy sau lệnh trên thì phần tử lớn nhất của dãy đã được di chuyển về cuối dãy, tức là phần tử này đã nằm đúng vị trí. Do đó trong vòng lặp tiếp theo thì không cần duyệt cả vòng lặp mà chỉ duyệt tới phần tử có chỉ số n − 3, tức là tại vòng duyệt tiếp theo chỉ cần thực hiện:

for j in range(n-2): # n là số phần tử của dãy.

nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]

Tổng quát, ở vòng duyệt thứ k thì công việc tại dòng 2 ở trên có thể viết như sau:

1 for j in range(n-k): # n là số phần tử của dãy.

2 nếu A[j] > A[j+1] thì đổi vị trí A[j] và A[j+1]

Bước 3. Chúng ta quay lại chi tiết hoá dòng 1 của chương trình tại B1.

Theo cách phân tích của bước 2 thì tại dòng 1 chỉ cần lặp đúng n – 1 lần thì dãy sẽ được sắp xếp xong. Như vậy dòng 1 có thể biểu diễn bằng lệnh Python: for i in range(n - 1):

Với mỗi i ở vòng lặp trên thì số thứ tự lần lặp sẽ là i+1 (do vòng lặp trên bắt đầu từ 0), do đó phải thay k ở dòng phía dưới (xem B2) bằng i + 1. Như vậy chúng ta có:

1 for i in range(n-1):

2 for j in range(n-i-1):

3 Nếu A[j] > A[j+1] thì đổi chỗ A[j],A[j+1]

Bước 4. Cuối cùng chúng ta sẽ chi tiết hoá công việc tại dòng 3 của chương trình trên và thu được phiên bản hoàn chỉnh của thuật toán sắp xếp nổi bọt.

1 def bubbleSort (A)

2 n = len(A)

3 for i in range(n-1):

Lời giải sách bài tập Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình hay khác:

• Câu 26.1 trang 79 SBT Tin học 11: Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần? ....

• Câu 26.2 trang 79 SBT Tin học 11: Phương pháp thiết kế làm mịn dần chính là ....

• Câu 26.3 trang 79 SBT Tin học 11: Phát biểu sau về phương pháp làm mịn dần là đúng hay sai ....

• Câu 26.4 trang 79 SBT Tin học 11: Với một bài toán, chỉ có một phương pháp thiết kế làm mịn dần duy nhất ....

• Câu 26.5 trang 79 SBT Tin học 11: Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần ....

• Câu 26.6 trang 79 SBT Tin học 11: Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần ....

Xem thêm các bài giải sách bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

• SBT Tin học 11 Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần

• SBT Tin học 11 Bài 28: Thiết kế chương trình theo mô đun

• SBT Tin học 11 Bài 29: Thực hành thiết kế chương trình theo mô đun

• SBT Tin học 11 Bài 30: Thiết lập thư viện cho chương trình

• SBT Tin học 11 Bài 31: Thực hành thiết lập thư viện chương trình

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải sgk Tin học 11 Kết nối tri thức
• Giải Chuyên đề Tin học 11 Kết nối tri thức
• Giải SBT Tin học 11 Kết nối tri thức
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)
• Giải lớp 11 Cánh diều (các môn học)

---