Sắp xếp chèn trực tiếp

Tư tưởng cơ bản

Thuật toán sắp xếp chèn trực tiếp hoạt động bằng cách lần lượt chèn từng phần tử vào đúng vị trí trong dãy con đã được sắp xếp trước đó. Quá trình này tiếp tục cho đến khi tất cả các phần tử được chèn vào vị trí thích hợp.

Giải thích cách thực hiện

Sử dụng ba biến: vị_trí_cuối, vị_trí_kế và giá_trị_tạm. Biến vị_trí_cuối trỏ đến phần tử đầu dãy, giá_trị_tạm lưu giá trị tại vị_trí_kế. Nếu giá trị tại vị_trí_cuối lớn hơn giá_trị_tạm, dịch chuyển phần tử và giảm vị_trí_cuối. Cuối cùng, chèn giá_trị_tạm vào vị trí thích hợp.

Độ phức tạp thời gian: O(n²)

Độ phức tạp không gian: O(1)

Triển khai mã nguồn

void SapXepChen(int* mang, int kich_thuoc) {
    for (int i = 0; i < kich_thuoc - 1; i++) {
        int vi_tri_cuoi = i;
        int gia_tri_tam = mang[vi_tri_cuoi + 1];
        
        while (vi_tri_cuoi >= 0) {
            if (mang[vi_tri_cuoi] > gia_tri_tam) {
                mang[vi_tri_cuoi + 1] = mang[vi_tri_cuoi];
                vi_tri_cuoi--;
            } else {
                break;
            }
        }
        mang[vi_tri_cuoi + 1] = gia_tri_tam;
    }
}

Sắp xếp Shell

Tư tưởng cơ bản

Thuật toán Shell Sort cải tiến từ sắp xếp chèn bằng cách chia dãy thành các nhóm con với khoảng cách giảm dần. Ban đầu sử dụng khoảng cách lớn, sau đó giảm dần cho đến khi khoảng cách bằng 1.

Giải thích cách thực hiện

Khởi tạo khoảng cách gap = n, sau đó liên tục giảm gap theo công thức gap = gap/3 + 1. Ở mỗi bước, thực hiện sắp xếp chèn trên các phần tử cách nhau gap đơn vị. Khi gap = 1, thuật toán trở thành sắp xếp chèn thông thường.

Độ phức tạp thời gian: O(N¹·³)

Độ phức tạp không gian: O(1)

Triển khai mã nguồn

void SapXepShell(int* mang, int kich_thuoc) {
    int khoang_cach = kich_thuoc;
    
    while (khoang_cach > 1) {
        khoang_cach = khoang_cach / 3 + 1;
        
        for (int i = 0; i < kich_thuoc - khoang_cach; i++) {
            int vi_tri_cuoi = i;
            int gia_tri_tam = mang[vi_tri_cuoi + khoang_cach];
            
            while (vi_tri_cuoi >= 0) {
                if (mang[vi_tri_cuoi] > gia_tri_tam) {
                    mang[vi_tri_cuoi + khoang_cach] = mang[vi_tri_cuoi];
                    vi_tri_cuoi -= khoang_cach;
                } else {
                    break;
                }
            }
            mang[vi_tri_cuoi + khoang_cach] = gia_tri_tam;
        }
    }
}

Sắp xếp nổi bọt

Tư tưởng cơ bản

Thuật toán sắp xếp nổi bọt hoạt động bằng cách so sánh và đổi chỗ các phần tử liền kề. Các phần tử lớn dần "nổi" lên vị trí cuối dãy qua mỗi lượt duyệt.

Giải thích cách thực hiện

Sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài giảm dần phạm vi duyệt, vòng lặp trong so sánh và đổi chỗ các phần tử liền kề. Biến kiem_tra_doi_cho giúp tối ưu hóa bằng cách dừng sớm nếu dãy đã được sắp xếp.

Độ phức tạp thời gian: O(n²)

Độ phức tạp không gian: O(1)

Triển khai mã nguồn

void DoiCho(int* a, int* b) {
    int tam = *a;
    *a = *b;
    *b = tam;
}

void SapXepNoiBot(int* mang, int kich_thuoc) {
    for (int cuoi = kich_thuoc; cuoi > 0; cuoi--) {
        int kiem_tra_doi_cho = 0;
        
        for (int i = 1; i < cuoi; i++) {
            if (mang[i - 1] > mang[i]) {
                DoiCho(&mang[i - 1], &mang[i]);
                kiem_tra_doi_cho = 1;
            }
        }
        
        if (kiem_tra_doi_cho == 0) break;
    }
}