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

Hi xin chào mọi người nha, trước khi đọc bài này, xin mời bạn tham khảo bài Tổng hợp một số thuật toán cơ bản về sắp xếp - Phần 1 . Ở  Bài này, mình sẽ giới thiệu với bạn các thuật toán sắp xếp nhanh hơn, có thể giải quyết được những bài toán với số lượng phần tử lớn hơn.

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

Thuật toán sắp xếp nhanh - Quick Sort

Tư tưởng chính của thuật toán sắp xếp này là: chọn ra một phần tử làm trung gian, phần tử có giá trị nhỏ hơn trung gian thì cho sang bên trái phần tử trung gian, phần tử có giá trị lớn hơn trung gian thì cho sang bên phải phần tử trung gian.

void QuickSort(int *a, int left, int right)
{
    int l = left, r = right;
    int pivot = a[(l + r) / 2];

    while(l <= r)
    {
        while(a[l] < pivot) l++;

        while(a[r] > pivot) r--;

        if(l <= r)
        {
            swap(a[l], a[r]);
            l++;
            r--;
        }
    }

    if(left < r)
        Quick(a, left, r);

    if(l < right)
        Quick(a, l, right);
}

Thuật toán sắp xếp trộn - Merge sort

// Hàm này dùng để trộn 2 phần đã được sắp xếp với nhau
void Merge(int *a, int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    int *tmp = new T[right - left + 1];

    while(l <= m && r <= right)
    {
        if(a[l] < a[r]) tmp[k++] = a[l++];
        else tmp[k++] = a[r++];
    }

    while (l <= m) tmp[k++] = a[l++];

    while (r <= right) tmp[k++] = a[r++];

    for(int i = 0; i < k; i++)
        a[i+left] = tmp[i];

    delete[] tmp;
}

// Chia dãy đã cho thành 2 phần cho đến đi không chia được nữa
// Sau khi chia làm 2 phần, sắp xếp từng phần, rồi trộn lại với nhau
void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right) / 2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, right);
        Merge(a, left, m, right);
    }
}

Thuật toán sắp xếp vun đống - Heap sort

Thuật toán xếp vun đống và thuật toán sắp xếp trộn ở trên có độ phức tạp là N.Log(N) nên chạy rất nhanh. Với thuật toán này, các phần tử trong mảng được đặt ở vị trí mô tả cây nhị phân đầy đủ. Tức là nếu chỉ số các phần tử là 0, 1, 2,… thì tại phần tử thứ i sẽ có 2 nút con của nó là tại phần tử thứ 2i + 1 và 2i + 2.

// Sắp xếp lại cây, sao cho phần tử cha luôn lớn hơn phần tử con của nó
void Heapify(int *a, int N, int i)
{
    int Left = 2*i + 1, Right = 2*i + 2, Largest;

    if(Left < N && a[Left] > a[i]) Largest = Left;
    else Largest = i;

    if(Right < N && a[Right] > a[Largest]) Largest = Right;

    if(Largest != i)
    {
        swap(a[i], a[Largest]);
        Heapify(a, N, Largest);
    }
}

// Xây dựng mô hình cây nhị phân sao cho phần tử cha luôn lớn hơn phần tử con
void BuildHeap(int *a, int N)
{
    for(int i = N/2-1; i >= 0; i--)
        Heapify(a, N, i);
}

// Hàm chính
void Heap(int *a, int N)
{
    BuildHeap(a, N);

    for(int i = N - 1; i >= 0; i--)
    {
        // cho phần tử lớn nhất xuống dưới cùng,
        // sau đó, cập nhật lại cây
        swap(a[i], a[0]);
        Heapify(a, i, 0);
    }
}

okii và phía trên là những thuật toán sấp xếp nhanh hơn và tối ưu hơn so với phần 1, nếu như các bạn thấy hay thì hãy comment bên dưới để giúp website của mình tăng tương tác nhé.