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

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;
    }
}