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
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.
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):
Xem thêm các bài giải SBT Tin học 11 Kết nối tri thức hay, chi tiết khác: