1. Ý tưởng thuật toán sắp xếp trộn

Câu hỏi. Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hoà, Lâm, Mai. Em hãy giúp thầy giáo yêu cầu 5 bạn thực hiện lần lượt các bước trong hai giai đoạn sau để sắp xếp hàng tăng dần theo chiều cao từ trái sang phải.

Vận dụng

Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biểu diễn khiêu vũ tập thể theo cặp (nam, nữ). Thầy giáo chủ nhiệm chọn ra n bạn nam có chiều cao A0, A1,...An-1, đứng thành một hàng ngang và n bạn nữ có chiều cao B0, B1,...Bn-1 đứng thành một hàng ngang để ghép thành nở cặp (nam. nữ). Để tiện ghép cặp, thầy giáo sắp xếp lại vị trí đứng các bạn nam trong hàng theo thứ tự chiều cao tăng dần và vị trí đứng các bạn nữ trong hàng cũng theo thứ tự chiều cao tăng dần. Sau đó thầy giáo tiến hành ghép cặp bạn nam thấp nhất với bạn nữ thấp nhất, bạn nam thấp thứ hai với bạn nữ thấp thứ hai và cứ như vậy đến bạn nam cao nhất với bạn nữ cao nhất. Em hãy viết chương trình áp dựng thuật toán sắp xếp trộn đề giúp thầy giáo thực hiện công việc ghép cặp này.

Chương trình cần nhập vào một số nguyên n, tiếp theo nhập vào n giá trị A0, A1, An-1 và n giá trị B0, B1, Bn-1 Chương trình cần in ra n cặp số Ai, Bj (0<i, j <n-1) là cách xếp cặp (nam, nữ) theo mong muốn của thầy giáo ở trên.