SXCHON - 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 một mảng gồm n phần tử a1, a2,..., an , giải thuật sắp xếp chọn (Selection Sort) thực hiện qua n-1 bước. Tại mỗi bước chọn ra phần tử nhỏ nhất trong các phần tử còn lại và hoán vị về đầu. 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: [2]  5  [8]  7  9  3

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

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

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

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

      (Dấu [] đánh dấu hai phần tử sau khi được hoán vị của từng bước. Tại bước 4, số 7 là phần tử nhỏ nhất trong ba số 7, 9, 8, tuy nhiên 7 đã nằm ở đầu nên không hoán vị)

      Cho mảng n phần tử bất kỳ, bạn hãy cho biết tình trạng của mảng sau mỗi bước thực hiện như trên.

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 a1, a2,..., an (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

- Tại dòng thứ i là n số cách nhau một khoảng trắng thể hiện tình trạng của mảng sau bước sắp xếp thứ i, có đánh dấu 2 số được hoán vị bằng cặp dấu [] (xem ví dụ).

Ví dụ

  • input
    6
    8 5 2 7 9 3
    output
    [2] 5 [8] 7 9 3
    2 [3] 8 7 9 [5]
    2 3 [5] 7 9 [8]
    2 3 5 [7] 9 8
    2 3 5 7 [8] [9]
Back to Top