[Phần 1] Tổng hợp một số thuật toán cơ bản về sắp xếp

Chú ếch ngốc nghếch

Jos Hoàng Tiên tao nghe nói mày đang học bí kíp luyện rồng! Chia sẻ cho tao ít đi.

Jos Hoàng Tiên

Được! Một số bí kíp mà tao tìm được trong WordPress đây.

Hôm nay, mình sẽ chia sẻ với bạn một số thuật toán cơ bản về sắp xếp. Những thuật toán sau thường dễ để triển khai, tuy nhiên thì độ phức tạp của chúng là N^2. Vì vậy, những thuật toán này chỉ áp dụng cho những bài toán với số lượng phần tử nhỏ. Với những bài toán có số lượng phần tử lớn thì ta sẽ sử dụng những thuật toán nhanh hơn - sẽ được giới thiệu ở phần sau.

Thuật toán sắp xếp chọn trực tiếp - Selection sort

void SelectionSort(int *a, int N)
{
    for(int i = 0; i < N - 1; i++)
    {
        int idmin = i;

        // Tìm ra phần tử có giá trị nhỏ nhất
        for(int j = i + 1; j < N; j++)
            if(a[j] < a[idmin])
                idmin = j;

        // Đổi chỗ phần tử đầu tiên của dãy còn lại với phần tử nhỏ nhất
        swap(a[i], a[idmin]);
    }
}

Thuật toán sắp xếp chèn trực tiếp - Insertion sort

void InsertionSort(int *a, int N)
{
    int pos, x;

    for(int i = 1; i < N; i++)
    {
        pos = i - 1;
        x = a[i];

        // giả sử dãy a[0], a[1], ... , a[i] đã sắp xếp
        // bắt đầu từ a[i], duyệt về đầu mảng và tìm vị trí thích hợp cho a[i]
        while(pos >= 0 && a[pos] > x)
        {
            a[pos + 1] = a[pos];
            pos--;
        }

        a[pos+1] = x;
    }
}

Thuật toán sắp xếp chèn trực tiếp dựa trên tìm kiếm nhị phân - Binary insertion sort

void BinaryInsertionSort(int *a, int N)
{
    int l, r, m, x;

    for(int i = 1; i < N; i++)
    {
        l = 0;
        r = i - 1;
        x = a[i];

        // Tương tự như Insertionsort nhưng ở đây
        // ta dựa vào tìm kiếm nhị phân để xác định
        // vị trí phù hợp cho a[i] được nhanh hơn
        while (l <= r)
        {
            m = (l + r) / 2;
            if(a[m] > x) r = m - 1;
            else l = m + 1;
        }

        for(int j = i; j > l; j--)
            a[j] = a[j-1];

        a[l] = x;
    }
}

Thuật toán sắp xếp đổi chỗ trực tiếp - Interchange sort

void InterChangeSort(int *a, int N)
{
    for(int i = 0; i < N - 1; i++)
        for(int j = i + 1; j < N; j++)
            if(a[j] < a[i])
                swap(a[j], a[i]);
}

Thuật toán sắp xếp nổi bọt - Bubble sort

void BubbleSort(int *a, int N)
{
    for(int i = 0; i < N-1; i++)
        for(int j = N-1; j > i; j--)
            if(a[j] < a[j-1])
                swap(a[j], a[j-1]);
}

Thuật toán sắp xếp Shaker sort

void ShakerSort(int *a, int N)
{
    // Thuật toán cải tiến thuật toán sắp xếp nổi bọt
    // Bình thường khi ta sắp xếp nổi bọt, giả sử tăng dần
    // Thì phần tử nhỏ nhất sẽ được dồn về trái, dần dần cho đến hết.
    // Còn với thuật toán này ta sẽ dồn phần tử nhỏ nhất về trái, phần tử lớn lớn sang phải đồng thời
    int left, right, k;

    left = 0;
    right = N-1;
    k = N-1;

    while(left < right)
    {
        for(int j = right; j > left; j--)
        {
            if(a[j] < a[j-1])
            {
                swap(a[j], a[j-1]);
                k = j;
            }
        }
        left = k;

        for (int j = left; j < right; j++)
        {
            if (a[j] > a[j+1])
            {
                swap(a[j], a[j+1]);
                k = j;
            }
        }
        right = k;
    }
}