Sắp xếp giữ nguyên hai đầu mảng (VT11)

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Mã bài VT11

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử. Hãy sắp xếp mảng theo thứ tự tăng dần (không giảm), nhưng giữ nguyên vị trí của phần tử đầu tiên và phần tử cuối cùng. Nói cách khác, chỉ sắp xếp các phần tử từ vị trí thứ $2$ đến vị trí thứ $n - 1$.

Em hãy tự viết thuật toán sắp xếp, không dùng hàm sắp xếp có sẵn.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$.
• Dòng thứ hai gồm $n$ số nguyên $A_1, A_2, \ldots, A_n$, cách nhau bởi dấu cách.

Kết quả:

In ra mảng sau khi sắp xếp trên một dòng, các phần tử cách nhau một dấu cách.

Giới hạn:

• $3 \le n \le 2000$
• $|A_i| \le 10^9$

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5
5 3 2 4 1

Ví dụ 1 – output

5 2 3 4 1

Giải thích:

• Giữ nguyên $5$ ở đầu và $1$ ở cuối; đoạn giữa $3, 2, 4$ được sắp thành $2, 3, 4$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Ý tưởng

Đây vẫn là sắp xếp tăng dần, chỉ khác là đoạn cần sắp là A[1..n-2] (bỏ phần tử đầu A[0] và cuối A[n-1]). Thầy dùng sắp xếp chọn trên đoạn đó: $i$ chạy từ 1 tới $n-3$, $j$ chạy từ $i+1$ tới $n-2$.

Ví dụ $5, 3, 2, 4, 1$: đoạn giữa $3, 2, 4$ sắp thành $2, 3, 4$ → 5 2 3 4 1.

Lưu ý / bẫy thường gặp

• Sắp xếp cả mảng, hoặc lỡ đưa phần tử đầu / cuối vào đoạn sắp xếp.
• Giới hạn vòng lặp lệch một đơn vị (j < n - 2) bỏ sót phần tử A[n-2].
• Sắp xếp giảm dần thay vì tăng dần.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇