SXCHEN - Sắp xếp chèn
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

      Để sắp xếp tăng dần một mảng n phần tử a0, a1,..., an-1 (chỉ số bắt đầu từ 0). thuật toán sắp xếp chèn thực hiện n -1 bước. Tại bước i, chèn phần tử ai vào các phần tử a0, a1,..., ai-1 sao cho dãy kết quả a0, a1,..., ai là tăng dần. Ví dụ minh họa:

      Sắp xếp mảng 6 phần tử:  8  5  2  7  9  3

        Sau bước 1: 5  8  2  7  9  3

        Sau bước 2: 2  5  8  7  9  3

        Sau bước 3: 2  5  7  8  9  3

        Sau bước 4: 2  5  7  8  9  3

        Sau bước 5: 2  3  5  7  8  9

      (Tại bước 1, số 5 chèn vào vị trí 0; tại bước 2, số 2 được chèn vào vị trí 0; tiếp theo, số 7 được chèn vào vị trí 2; tiếp theo số 9 giữ nguyên vị trí 4, cuối cùng số 3 chèn vào vị trí 1)

      Cho mảng n phần tử bất kỳ, bạn hãy cho biết tại mỗi bước thực hiện như trên thì số nào được chèn vào vị trí nào nhé.

Dữ liệu nhập:

- Dòng đầu tiên là số nguyên n (2 ≤ n ≤ 20) là số phần tử của mảng.

- Dòng tiếp theo gồm n số nguyên a0, a1,..., an-1 (1 ≤ ai ≤ 100), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất: gồm n - 1 dòng thể hiện n - 1 bước

- Tại dòng i là 2 số nguyên ai và k cách nhau một khoảng trắng. k là vị trí cần chèn của ai

Ví dụ

  • input
    6
    8 5 2 7 9 3
    output
    5 0
    2 0
    7 2
    9 4
    3 1
Back to Top