Đếm số lần hoán đổi của sắp xếp nổi bọt
Sắp xếp nổi bọt so sánh từng cặp kề nhau và hoán đổi khi sai thứ tự. Số lần hoán đổi nó thực hiện đúng bằng số cặp nghịch thế của mảng — một thước đo mức độ lộn xộn của dữ liệu, th…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: arrays-and-loops, swap.
Nội dung đề bài
Mô tả bài toán
Sắp xếp nổi bọt so sánh từng cặp kề nhau và hoán đổi khi sai thứ tự. Số lần hoán đổi nó thực hiện đúng bằng số cặp nghịch thế của mảng — một thước đo mức độ lộn xộn của dữ liệu, thường dùng để phân tích chi phí sắp xếp.
Yêu cầu
Đọc từ stdin: dòng 1 là N; dòng 2 là N số nguyên. Mô phỏng sắp xếp nổi bọt tăng dần và in ra số lần hoán đổi đã thực hiện.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không truyền lời nhắc vào
input(). Lời nhắc sẽ bị in vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Hai dòng: N và dãy N số nguyên.
Output
Một số nguyên: tổng số lần hoán đổi.
Ràng buộc
- 1 ≤ N ≤ 2000; |ai| ≤ 109.
Ví dụ 1
Input
5
5 1 4 2 8Output
4
Các cặp nghịch thế là (5,1), (5,4), (5,2), (4,2) — đúng 4 lần hoán đổi.Ví dụ 2
Input
3
1 2 3Output
0
Mảng đã tăng dần nên không cần hoán đổi lần nào.Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.