Queue Sort
Sau một buổi học Cấu trúc dữ liệu và giải thuật với thầy
, nqson vừa nghĩ ra một thuật toán Queue Sort có nội dung như sau:Cho một dãy số gồm n số hạng khác nhau, ta cần tạo ra 2 hảng đợi để sắp xếp n số hạng đó. Hàng đợi đầu tiên (
- Trường hợp 1: Nếu
đang rỗng, ta lấy một tử đầu tiên của cho vào - Trường hợp 2: Nếu phần tử đầu tiên của cả hai hàng đợi đều lớn hơn phần tử cuối cùng của
, ta lấy phần tử bé hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối - Trường hợp 3: Nếu phần tử đầu tiên của
lớn hơn phần tử cuối cùng của cả hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng lớn hơn - Trường hợp 4: Nếu một trong hai phần tử đầu tiên của hai hàng đợi lớn hơn phần tử cuối cùng của
, ta lấy phần tử lớn hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối - Trường hợp 5: Nếu phần tử đầu tiên của
lớn hơn một trong hai phần tử cuối cùng của hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng bé hơn - Trường hợp 6: Nếu tất cả các trường hợp trên không thỏa mãn, ta lấy phần tử ở đầu hàng đợi có giá trị bé hơn ra khỏi hàng đợi rồi thêm nó vào cuối
Thực hiện đến khi
In ra tổng số lượng các bước trên.
Giới hạn:
Đầu vào
Dòng đầu tiên là một số tự nhiên
Dòng tiếp theo chứa
Đầu ra
In ra tổng số lượng các bước để có thể sắp xếp thành công dãy số
Ví dụ 1:
Đầu vào
Copy
5
1 2 3 4 5
Đầu ra
Copy
5
Ví dụ 2:
Đầu vào
Copy
3
2 3 1
Đầu ra
Copy
7
Giải thích
Copy
Bắt đầu:
qu1: 2 3 1
qu2:
B1:
qu1: 3 1
qu2: 2
B2:
qu1: 3 1 2
qu2:
B3:
qu1: 1 2
qu2: 3
B4:
qu1: 1 2 3
qu2:
B5:
qu1: 2 3
qu2: 1
B6:
qu1: 3
qu2: 1 2
B7:
qu1:
qu2: 1 2 3
Comments