Chap 7: Sorting⚓︎

void InsertionSort(ElementType A[], int N)
{
    int j, P;
    ElementType Tmp;

    for (P = 1; P < N; P++)
    {
        Tmp = A[P] // the next coming card
        for (j = P; j > 0 && A[j - 1] > Tmp; j--)
            A[j] = A[j - 1];
        // shift sorted cards to provide a position for the new coming card
        A[j] = Tmp; // place the new card at the proper position
    } // end for-P-loop
}

void Shellsort(ElementType A[], int N)
{
    int i, j, increment;
    ElementType Tmp;
    for (increment = N / 2; increment > 0; increment /= 2)
        // h sequence
        for (i = increment; i < N; i++)
        { // insertion sort
            Tmp = A[i];
            for (j = i; j >= increment; j -= increment)
                if (Tmp < A[j - increment])
                    A[j] = A[j - increment];
                else
                    break;
                A[j] = Tmp;
        } // end for-l and for-increment loop
}

// 这里的 PercDown 函数与 Chap 6 给出的稍有不同（索引的标注发生变化）
#define LeftChild(i) (2 * (i) + 1)

void PercDown(ElementType A[], int i, int N)
{
    int Child;
    ElementType Tmp;

    for (Tmp = A[i]; LeftChild(i) < N; i = Child)
    {
        Child = LeftChild(i);
        if (Child != N - 1 && A[Child + 1] > A[Child])
            Child++;
        if (Tmp < A[Child])
            A[i] = A[Child];
        else
            break;
    }
    A[i] = Tmp;
}

void Heapsort(ElementType A[], int N)
{
    int i;
    for (i = N / 2; i >= 0; i--)  // BuildHeap
        PercDown(A, i, N);
    for (i = N - 1; i > 0; i--)   // DeleteMax
    {
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}

void MergeSort(ElementType A[], int N)
{
    ElementType *TmpArray;
    TmpArray = (ElementType *)malloc(N * sizeof(ElementType));
    if (TmpArray != NULL)
    {
        MSort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    }
    else FatalError("No space for tmp array!!!");
}

void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)
{
    int Center;
    if (Left < Right)
    {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center + 1, Right);
        Merge(A, TmpArray, Left, Center + 1, Right);
    }
}

// Lpos = start of left half, Rpos = start of right half
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
    int i, LeftEnd, NumElements, TmpPos;
    LeftEnd = Rpos - 1;
    TmpPos = Lpos;
    NumElements = RightEnd - Lpos + 1;
    while (Lpos <= LeftEnd && Rpos <= RightEnd) // main loop
        if (A[Lpos] <= A[Rpos])
            TmpArray[TmpPos++] = A[Lpos++];
        else
            TmpArray[TmpPos++] = A[Rpos++];
    while (Lpos <= LeftEnd) // Copy rest of first half
        TmpArray[TmpPos++] = A[Lpos++];
    while (Rpos <= RightEnd) // Copy rest of second half
        TmpArray[TmpPos++] = A[Rpos++];
    for (i = 0; i < NumElements; i++, RightEnd--)
        // Copy TmpArray back
        A[RightEnd] = TmpArray[RightEnd];
}

void Quicksort(ElementType A[], int N)
{
    Qsort(A, 0, N - 1);
    // A: the array
    // 0: Left index
    // N - 1: Right index
    // Return median of Left, Center, and Right
    // Order these and hide the pivot
}

void Qsort(ElementType A[], int Left, int Right)
{
    int i, j;
    ElementType Pivot;

    if (Left + Cutoff <= Right) // if the sequence is not too short
    {
        Pivot = Median3(A, Left, Right);  // select pivot
        i = Left;                         // (1)
        j = Right - 1;                    // (2)
        for (;;)
        {
            while (A[++i] < Pivot) {}     // scan from left
            while (A[--j] > Pivot) {}     // scan from right
            if (i < j)
                Swap(&A[i], &A[j]);       // adjust partition
            else break;                   // partition done
        }
        Swap(&A[i], &A[Right - 1]);       // restore pivot
        Qsort(A, Left, i - 1);            // recursively sort left part   
        Qsort(A, i + 1, Right);           // recursively sort right part  
    }  // end if - the sequence subarray
    else
        InsertionSort(A + Left, Right - Left + 1);
}

ElementType Median3(ElementType A[], int Left, int Right)
{
    int Center = (Left + Right) / 2;
    if (A[Left] > A[Center])
        Swap(&A[Left], &A[Center]);
    if (A[Left] > A[Right])
        Swap(&A[Left], &A[Right]);
    if (A[Center] > A[Right])
        Swap(&A[Center], &A[Right]);
    // Invariant: A[Left] <= A[Center] <= A[Right]
    Swap(&A[Center], &A[Right - 1]);
    // only need to sort A[Left + 1] .. A[Right - 2]
    // 因为我们已经知道 A[Left] 比 pivot 小，A[Right] 比 pivot 大
    // 所以回到 Qsort 函数后，我们无需改变 A[Left] 和 A[Right] 的顺序
    return A[Right - 1]; // Return pivot
}

// Places the kth smallest element in the kth position
// Because arrays start at 0. this will be index k-1
void Qselect(ElementType A[], int k, int Left, int Right)
{
    int i, j;
    ElementType Pivot;

    if (Left + Cutoff <= Right)
    {
        Pivot = Median3(A, Left, Right);
        i = Left; j = Right - 1;
        for (;;)
        {
            while (A[++i] < Pivot) {}
            while (A[--j] > Pivot) {}
            if (i < j)
                Swap(&A[i],  &A[j]);
            else
                break;
        }
        Swap(&A[i], &A[Right - 1]);

        if (k <= i)
            Qselect(A, k, Left, i - 1);
        else if (k > i + 1)
            Qselect(A, k, i + 1, Right);
    }
    else 
        InsertionSort(A + Left, Right - Left + 1);
}