Câu hỏi/bài tập:
Dựa trên minh họa diễn biến từng bước của thuật toán sắp xếp nổi bọt được trình bày như ở Hình 1, em hãy nêu tóm tắt ý tưởng của thuật toán này.
Dựa vào kiến thức đã học.
Advertisements (Quảng cáo)
Xét một mảng gồm 5 số nguyên: a1, a2, …, a5.
Với cách sắp xếp không giảm từ trái qua phải, mục đích của chúng ta là đưa dần các số lớn nhất về cuối dãy (ngoài cùng bên phải).
Bắt đầu từ vị trí số 1, xét lần lượt từng cặp 2 phần tử, nếu phần tử bên phải nhỏ hơn phần tử bên trái, ta sẽ thực hiện đổi chỗ 2 phần tử này, nếu không, xét tiếp cặp tiếp theo. Với cách làm như vậy, phần tử nhỏ hơn sẽ “nổi” lên, còn phần tử lớn hơn sẽ “chìm” dần và về bên phải.
Khi kết thúc vòng thứ nhất, ta sẽ đưa được phần tử lớn nhất về cuối dãy. Sang vòng thứ hai, ta tiếp tục bắt đầu ở vị trí đầu tiên như vậy và đưa được phần tử lớn thứ hai về vị trí thứ hai ở cuối dãy ...