HSG THPT TPHCM 2023 - Thuật Toán Sắp Xếp
Xem dạng PDF
Sắp xếp là một trong những thuật toán phổ biến nhất trong khoa học máy tính. An vừa được giới thiệu các thuật toán sắp xếp và biết rằng thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp trung bình là ~O(n \log{n})~. Tuy nhiên An vẫn muốn sáng tạo một thuật toán sắp xếp mới và xem thử liệu nó có tốt hơn Quick Sort. Xét một mảng ~n~ số nguyên, mỗi phần tử có giá trị từ ~1~ đến ~n~ và mỗi giá trị chỉ xuất hiện một lần trong mảng. Thuật toán này sẽ sắp xếp mảng trên trong ~n~ bước như sau:
Bước 1: phần tử có giá trị ~1~ sẽ được chuyển đến vị trí ~1~ bằng cách liên tiếp hoán đổi vị trí với phần tử liền kề với nó.
Bước 2: phần tử có giá trị ~n~ sẽ được chuyển đến vị trí ~n~ bằng cách như bước ~1~.
Bước 3: phần tử có giá trị ~2~ sẽ được chuyển đến vị trí ~2~ bằng cách tương tự.
Bước 4: phần tử có giá trị ~n - 1~ sẽ được chuyển đến vị trí ~n - 1~ bằng cách tương tự.
Và cứ thể tiếp tục đến bước ~n~.
Tổng quát hơn, ở bước lẻ, An sẽ chọn phần tử có giá trị nhỏ nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó. Ở bước chẵn An sẽ chọn phần tử có giá trị lớn nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó.
Yêu cầu: Viết chương trình cho biết số lần hoán đổi vị trí các phần tử tại mỗi bước của thuật toán trên.
Input
Dòng đầu tiên chứa một số nguyên ~n~ cho biết số lượng phần tử của mảng.
Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~a_i~ ~(1 \leq a_i \leq n)~ cho biết giá trị của phần tử thứ ~i~ trong mảng. Các giá trị ~a_i~ không lặp lại.
Output
- Gồm ~n~ số nguyên, số thứ ~i~ cho biết số lần hoán đổi vị trí các phần tử ở bước thứ ~i~ của thuật toán. Mỗi số ghi trên một dòng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50\%~ | ~n \leq 1000~ |
| 2 | ~20\%~ | ~n \leq 10000~ |
| 3 | ~30\%~ | ~n \leq 100000~ |
Sample Input 1
7
5
2
6
7
3
1
4
Sample Output 1
5
2
1
2
1
1
0
Bình luận
Ai giải thích test cho mik với TT. Số 2 cs thay đổi lần nào đâu mà output là 2...
Để có thể hiểu được test ví dụ thì bạn nên đọc kĩ đề và viết cái mảng ra để có cái nhìn đúng nhất.
Sau đây mình sẽ mô phỏng ~7~ bước của thuật toán sắp xếp của đề bài:
Mảng ban đầu: ~5, 2, 6, 7, 3, 1, 4~
Bước 1:
Di chuyển số ~1~ về vị trí ~1~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 5, 2, 6, 7, 3, 4~
Nhận thấy có ~5~ lượt hoán đổi của phần tử có giá trị ~1~, cho nên dòng đầu tiên in ~\textbf{5}~
Bước 2:
Di chuyển số ~7~ về vị trí ~7~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 5, 2, 6, 3, 4, 7~
Nhận thấy có ~2~ lượt hoán đổi của phần tử có giá trị ~7~, cho nên dòng thứ hai in ~\textbf{2}~
Bước 3:
Di chuyển số ~2~ về vị trí ~2~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 2, 5, 6, 3, 4, 7~
Nhận thấy có ~1~ lượt hoán đổi của phần tử có giá trị ~2~, cho nên dòng thứ ba in ~\textbf{1}~
Bước 4:
Di chuyển số ~6~ về vị trí ~6~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 2, 5, 3, 4, 6, 7~
Nhận thấy có ~2~ lượt hoán đổi của phần tử có giá trị ~6~, cho nên dòng thứ tư in ~\textbf{2}~
Bước 5:
Di chuyển số ~3~ về vị trí ~3~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 2, 3, 5, 4, 6, 7~
Nhận thấy có ~1~ lượt hoán đổi của phần tử có giá trị ~3~, cho nên dòng thứ năm in ~\textbf{1}~
Bước 6:
Di chuyển số ~5~ về vị trí ~5~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 2, 3, 4, 5, 6, 7~
Nhận thấy có ~1~ lượt hoán đổi của phần tử có giá trị ~5~, cho nên dòng thứ sáu in ~\textbf{1}~
Bước 7:
Di chuyển số ~4~ về vị trí ~4~:
Lần lượt tráo đổi các cặp sau (nhấn vào hộp dưới để hiện chi tiết):
Có được mảng cuối cùng như sau: ~1, 2, 3, 4, 5, 6, 7~
Nhận thấy có ~0~ lượt hoán đổi của phần tử có giá trị ~4~, cho nên dòng thứ bảy in ~\textbf{0}~
Tổng kết
Qua ~7~ bước trên ta in ra lần lượt số lượt hoán đổi của phần tử tại lượt đó: theo test ví dụ thì output in ra là:
Chúc bạn làm hiểu được đề bài và giải được bài!
nó in ra theo kiểu j mà thứ tự là 1 7 2 6 3 5 ... ý