Editorial for ptit019: Sắp xếp 3 số nguyên

Hiểu bài toán

Bài toán yêu cầu nhập vào 3 số nguyên a, b, c và in ra chúng theo thứ tự giảm dần (từ lớn đến bé). Dữ liệu đầu vào nằm trong khoảng từ 1 đến 100,000. Ví dụ: với input '2671 6575 17109', output mong đợi là '17109 6575 2671'.

Các cách tiếp cận

Cách Sử dụng biến trung gian và so sánh trực tiếp

#include "stdio.h"
#include "string.h"
#include "ctype.h" 
#define MAX_SIZE 10000



int main () {

    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);

    int min, max,middle;

    min = a;
    if (min > b)
    {
        min = b;
    }
    if (min > c)
    {
        min = c;
    }

     max = c;

    if ( max < b)
    {
        max = b;
    }
    if ( max < a)
    {
        max = a;
    }

    middle = a+b+c-max-min;

    printf("%d %d %d", max, middle, min);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này tìm giá trị lớn nhất (max) và nhỏ nhất (min) bằng cách so sánh từng cặp số. Giá trị còn lại (middle) được tính toán bằng cách lấy tổng của 3 số trừ đi max và min.

Các bước:

1. Khởi tạo min = a và max = c.
2. So sánh min với b và c để cập nhật giá trị nhỏ nhất.
3. So sánh max với b và a để cập nhật giá trị lớn nhất.
4. Tính middle = a + b + c - max - min.
5. In ra max, middle, min.

Ưu điểm: Hiệu quả về mặt tính toán, không cần dùng mảng hay cấu trúc phức tạp. Nhược điểm: Cần nhiều câu lệnh điều kiện so sánh.

Cách Sử dụng Bubble Sort (hoặc Selection Sort) trên mảng

#include <stdio.h>

int main(){
    int a[3];
    for(int i=0; i<3; i++){
        scanf("%d", &a[i]);
    }
    for(int i=0; i<3; i++){
        for(int j=0; j<2; j++){
            if(a[j]<a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(int i=0; i<3; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

• Time Complexity: O(1) (vì độ dài mảng cố định là 3)
• Space Complexity: O(1)

Sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) hoặc chọn lựa (Selection Sort) để sắp xếp mảng 3 phần tử theo thứ tự giảm dần.

Các bước:

1. Đọc 3 số vào mảng a.
2. Dùng vòng lặp lồng nhau để so sánh các phần tử kề nhau. Nếu phần tử trước nhỏ hơn phần tử sau thì hoán đổi vị trí. Với Bubble Sort giảm dần, điều kiện là a[j] < a[j+1]. Với Selection Sort, ta tìm phần tử lớn nhất đưa lên đầu.
3. In ra mảng sau khi sắp xếp.

Phương pháp này trong code mẫu thực chất là Bubble Sort hoặc tương tự. Nó dễ hiểu và tổng quát hóa cho nhiều số hơn.

Cách Sử dụng hàm qsort (Quick Sort) của thư viện chuẩn

#include<stdio.h>

void sort(int a[],int n){
    for (int i = 0; i < n - 1; i++){
        for (int j = i + 1;j < n; j++){
            if (a[i] < a[j]){
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
}
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int x[3];
    x[0] = a;
    x[1] = b;
    x[2] = c;
    sort(x,3);
    for (int i = 0;i < 3; i++){
        printf("%d ",x[i]);
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Code mẫu sử dụng hàm sort tự viết (thực chất là Selection Sort) để sắp xếp mảng.

Các bước:

1. Đọc a, b, c.
2. Lưu vào mảng x.
3. Gọi hàm sort(x, 3). Hàm này sử dụng vòng lặp kép để hoán đổi phần tử tại x[i] với x[j] nếu x[i] < x[j] (sắp xếp giảm dần).
4. In mảng.

Đây là cách tiếp cận theo hướng thuật toán sắp xếp chuẩn, dễ đọc và dễ sửa đổi nếu muốn sắp xếp thêm nhiều số khác.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Với số lượng phần tử cố định và rất nhỏ (chỉ 3), các thuật toán có độ phức tạp O(n^2) như Bubble Sort hay Selection Sort đều chạy gần như tức thời và được chấp nhận.
• Có thể tận dụng tính chất toán học: middle = total - max - min để tìm giá trị trung gian mà không cần sort.
• Việc sử dụng mảng giúp code dễ dàng mở rộng nếu yêu cầu thay đổi số lượng phần tử cần sắp xếp.

Lỗi thường gặp

• Lỗi in thừa dấu cách ở cuối dòng output (ví dụ in "17109 6575 2671 " thay vì "17109 6575 2671"). Các giải pháp trong bài đều xử lý đúng.
• Sai lệch thứ tự nếu chỉ so sánh từng cặp rời rạc mà không kiểm tra hết các trường hợp (ví dụ: chỉ so sánh a vs b, b vs c mà không so sánh a vs c). Các giải pháp dùng biến max/min hoặc sort đều tránh được lỗi này.
• Quên khai báo biến temp khi hoán đổi giá trị trong các thuật toán sort.