← Level 3 · Đọc hiểu & Tình huống FE
Thuật toán & giả mã Tình huống đọc hiểu Độ khó: Nâng cao Thời gian dự kiến: Khoảng 5 phút Cấp độ phù hợp: FE Level 3 (môn B)

Truy vết thuật toán sắp xếp nổi bọt (bubble sort)

Sắp xếp một mảng bằng cách liên tục so sánh và hoán đổi các phần tử liền kề được gọi là sắp xếp nổi bọt (bubble sort). Đoạn giả mã dưới đây sắp xếp mảng data theo thứ tự tăng dần.

○ mảng số nguyên: bubbleSort(mảng số nguyên: data)
  số nguyên: i, j, temp
  for (i từ 0 đến (số phần tử của data) - 2, tăng dần 1)
    for (j từ 0 đến (số phần tử của data) - 2 - i, tăng dần 1)
      if (data[j] lớn hơn data[j+1]) then
        temp ← data[j]
        data[j] ← data[j+1]
        data[j+1] ← temp
      endif
    endfor
  endfor
  return data

Giả sử mảng data = [5, 2, 4, 1].

Từ khóa

バブルソートばぶるそーとsắp xếp nổi bọt 交換こうかんhoán đổi (swap)

Câu hỏi

1

Trạng thái của data sau khi vòng lặp ngoài đầu tiên (i=0) kết thúc là gì?

Lựa chọn

  1. [2, 4, 1, 5]
  2. [1, 2, 4, 5]
  3. [2, 1, 4, 5]
  4. [5, 2, 4, 1]
Xem giải thích

Ở j=0, 5 và 2 hoán đổi → [2,5,4,1]; ở j=1, 5 và 4 hoán đổi → [2,4,5,1]; ở j=2, 5 và 1 hoán đổi → [2,4,1,5].

2

Có tổng cộng bao nhiêu lần hoán đổi cho đến khi sắp xếp hoàn tất?

Lựa chọn

  1. 3 lần
  2. 4 lần
  3. 5 lần
  4. 6 lần
Xem giải thích

i=0 thực hiện 3 lần hoán đổi, i=1 thực hiện 1 lần, i=2 thực hiện 1 lần, tổng cộng 5 lần.

3

Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán này là gì?

Lựa chọn

  1. O(n)
  2. O(n log n)
  3. O(n^2)
  4. O(2^n)
Xem giải thích

Với hai vòng lặp lồng nhau chạy khoảng n lần mỗi vòng, độ phức tạp là O(n^2).

Đăng nhập để lưu kết quả

Bạn có thể đọc miễn phí nội dung, câu hỏi và giải thích. Hãy đăng nhập để lưu kết quả và đưa vào hàng ôn tập cùng phân tích điểm yếu.

Đăng nhập để lưu