Câu hỏi:

13/07/2024 410

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.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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):

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. (ảnh 1)

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

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 mảng A (có n phần tử) và giá trị K. Cần tìm phần tử của A có giá trị bằng K. Nếu tìm thấy trả lại chỉ số của phần tử này (chỉ cần tìm một nghiệm), ngược lại trả về −1.

Bước 1. Thiết lập ý tưởng thiết kế ban đầu.

1 Duyệt các phần tử của mảng A từ trái sang phải.

2 Giả sử chỉ số đang duyệt là i, kiểm tra xem A[i] = K

hay không, nếu đúng thì dừng lại, trả về i.

3 Cuối cùng trả về -1.

Bước 2. Chi tiết hoá dòng 1 ở trên.

5 for i in range(len(A)):

Bước 3. Chi tiết hoá dòng 2 của ý tưởng thiết kế ban đầu.

7 if A[i] == K:

8

return i

Bước 4. Chi tiết hoá dòng 3 của ý tưởng thiết kế ban đầu.

return -1

Chương trình hoàn chỉnh:

def LinearSearch (A):

for i in range (A):

if A[i] == K:

return -1

return i

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay