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

// 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

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