Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Sắp xếp danh sách điểm thi bằng Comb Sort

    Phòng đào tạo cần sắp xếp danh sách điểm thi của nnn sinh viên theo thứ tự không giảm bằng thuật toán Comb Sort — biến thể cải tiến của Bubble Sort dùng khoảng cách (gap) co dần theo hệ số 1.31.31.3.

    Ý tưởng: ban đầu gap=ngap = ngap=n. Mỗi vòng, gap=⌊gap⋅10/13⌋gap = \lfloor gap \cdot 10 / 13 \rfloorgap=⌊gap⋅10/13⌋ (tối thiểu là 111). So sánh và đổi chỗ các cặp cách nhau gapgapgap vị trí. Lặp đến khi gap=1gap = 1gap=1 và không còn hoán đổi.

    Ví dụ: [5,3,8,1,2][5, 3, 8, 1, 2][5,3,8,1,2] → [1,2,3,5,8][1, 2, 3, 5, 8][1,2,3,5,8].

    • Định dạng đầu vào:

      Dòng 1: số nguyên nnn. Dòng 2: nnn số nguyên (cách nhau bởi khoảng trắng).

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, −109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai​≤109.

    • Định dạng đầu ra:

      Một dòng gồm nnn số đã sắp xếp tăng dần, cách nhau bởi một dấu cách.

    Ví dụ:

    Đầu vào:

    5
5 3 8 1 2

    Đầu ra:

    1 2 3 5 8

    Giải thích:

    Sau khi sắp xếp: 1 2 3 5 8.

    Đang tải editor...