Phân hoạch Lomuto (Quick Sort Partition)

Buổi 06 — Sắp xếp & Tìm kiếm sorting
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho dãy gồm $N$ số nguyên. Hãy thực hiện phép phân hoạch Lomuto với phần tử chốt (pivot) là phần tử cuối cùng $A[N-1]$: duyệt $j$ từ $0$ đến $N-2$, nếu $A[j] \le \text{pivot}$ thì tăng chỉ số $i$ và hoán đổi $A[i]$ với $A[j]$; cuối cùng hoán đổi $A[i+1]$ với $A[N-1]$. Hãy in ra chỉ số mới của pivot (0-indexed) và dãy số sau khi phân hoạch.

Dữ liệu vào

Dòng đầu chứa số nguyên dương $N$. Dòng thứ hai chứa $N$ số nguyên $A_0, A_1, \dots, A_{N-1}$.

Dữ liệu ra

Dòng đầu in chỉ số của pivot sau khi phân hoạch. Dòng thứ hai in $N$ số nguyên của dãy sau khi phân hoạch.

Ví dụ
Input Output
6\n10 80 30 90 40 50 2\n10 30 40 50 80 90
1\n7 0\n7
Giới hạn

$1 \le N \le 10^5$, $|A_i| \le 10^9$.

Draft saved