SXNHANH - Sắp xếp nhanh
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 A gồm n phần tử a1, a2,..., an, thuật toán sắp xếp nhanh (QuickSort) áp dụng phân hoạch để chia mảng A thành hai mảng con B và C sao cho bi ≤ cj (với mọi i,j). Có nhiều thuật toán phân hoạch, một trong số đó là thuật toán Lomuto. Thuật toán thực hiện như sau:

- Chọn phần tử tử cuối của mảng A làm chốt phân hoạch.

- Duyệt qua các phần tử của mảng A từ phần tử đầu đến phần tử kế cuối. Nếu phần tử nào nhỏ hơn hoặc bằng chốt thì hoán vị về đầu (đưa vào mảng B).

- Hoán vị chốt vào giữa sao cho chốt là phần tử phân định giữa B và C.

Ví dụ minh họa: phân hoạch 8 phần tử:  8  7  2  1  5  3  6  4. Chọn chốt phân hoạch là 4.

        Hoán vị 2 về đầu: 2  7  8  1  5  3  6  [4]

        Hoán vị 1 về đầu: 2  1  8  7  5  3  6  [4]

        Hoán vị 3 về đầu: 2  1  3  7  5  8  6  [4]

        Hoán vị chốt vô giữa: 2  1  3  [4]  5  8  6  7

(Các phần tử được gạch dưới ≤ 4 là mảng B, các phần tử còn lại ≥ 4 là mảng C)

Cho một mảng n phần tử bất kỳ, bạn hãy phân hoạch mảng trên dùng thuật toán Lomuto.

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:

- Là một dòng gồm n phần tử sau khi đã phân hoạch, mỗi phần tử cách nhau một khoảng trắng. Phần tử chốt được đánh dấu bằng cặp dấu [].

 

Ví dụ

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