Cho hai dãy số nguyên dương

Để giải bài toán này, ta có thể sử dụng thuật toán sắp xếp nổi bọt (bubble sort). Thuật toán này hoạt động bằng cách so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng không theo thứ tự. Ta lặp lại quá trình này cho đến khi không còn phần tử nào cần hoán đổi.

Dưới đây là mã giả của thuật toán:

1. Đọc dữ liệu đầu vào gồm n và hai dãy số a và b.
2. Khởi tạo một biến swapped = True để đánh dấu việc hoán đổi phần tử.
3. Lặp lại các bước 4-6 cho đến khi swapped = False.
4. Đặt swapped = False.
5. Lặp qua từng cặp phần tử liền kề trong dãy a.
6. Nếu phần tử thứ i lớn hơn phần tử thứ i+1, hoán đổi chúng và đặt swapped = True.
7. In ra từng cặp phần tử đã sắp xếp.

Dưới đây là mã giả của thuật toán trong Python:

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

swapped = True
while swapped:
swapped = False
for i in range(n-1):
if a[i] > a[i+1] or (a[i] == a[i+1] and b[i] >= b[i+1]):
a[i], a[i+1] = a[i+1], a[i]
b[i], b[i+1] = b[i+1], b[i]
swapped = True

for i in range(n):
print(a[i], b[i])

Độ phức tạp của thuật toán này là O(n^2) trong trường hợp xấu nhất, với n là số lượng phần tử trong dãy.