UVa 10810 - Ultra-QuickSort

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

排序過程總共把 相鄰 的數字交換了幾次?

Solution

雖然題目出現 quick sort 卻是用 merge sort 來解…

在 merge 的過程中計算相鄰兩數字交換的次數，兩排序好的子序列 merge 到同一序列時，可以計算右邊的數字移動了多少來得到交換的次數。

在 assign 排序好的序列時可以用 pointer 加速。

int *temp = p_num;
p_num = p_sortArr;
p_sortArr = temp;

以下分別為 iterative 和 recursive 的 merge sort。

p.s. 次數要用 long long ，以免 overflow 。

Code

iterative (highlight 出了點問題，可至 github 觀看)

UVa 10810UVa 10810(1) - Ultra-QuickSort

#include<cstdio>
#include<cstdlib>
#define N 500000
typedef long long LL;

inline int getNum();
LL merge_sort(int* p_num, int* p_sortArr, int len);//iterative version
int main()
{
    int* p_sortArr = (int*)malloc(N*sizeof(int));
    int* p_num = (int*)malloc(N*sizeof(int));

    int n;

    while (n = getNum())
    {
        for (int i = 0; i < n; i++)
            p_num[i] = getNum();
        printf("%lld\n", merge_sort(p_num, p_sortArr, n));
    }

    free(p_sortArr);
    free(p_num);
    return 0;
}
inline int getNum()
{
    char c;
    int n = 0;
    while ((c = getchar()) != '\n')
        n = n * 10 + c - '0';
    return n;
}
LL merge_sort(int* p_num, int* p_sortArr, int len)
{
    LL swap = 0;

    for (int seg = 1; seg < len; seg <<= 1)//一半子序列的長度
    {
        int m = seg << 1;//子序列的長度
        for (int start = 0; start < len; start += m)
        {
            int left = start;
            int mid = start + seg - 1 > len - 1 ? len - 1 : start + seg - 1;
            int right = start + m - 1 > len - 1 ? len - 1 : start + m - 1;

            int s1 = left, end1 = mid;
            int s2 = mid + 1, end2 = right;

            int idx = left;
            while (s1 <= end1&&s2 <= end2)
            {
                if (p_num[s1] <= p_num[s2])
                    p_sortArr[idx++] = p_num[s1++];
                else
                {
                    p_sortArr[idx++] = p_num[s2++];
                    swap += end1 - s1 + 1;//次數為左子序列剩下的還沒排序的數字
                }
            }          
            while (s1 <= end1)
                p_sortArr[idx++] = p_num[s1++];
            while (s2 <= end2)
                p_sortArr[idx++] = p_num[s2++];
        }

        //將原本的 ptr 指向排序好的
        int *temp = p_num;
        p_num = p_sortArr;
        p_sortArr = temp;
    }
    return swap;
}

recursive

UVa 10810UVa 10810(2) - Ultra-QuickSort

#include<cstdio>
#define N 500000

int num[N];
inline int getNum();
void merge_sort(int left, int right, long long& swap);//recursive version
int main()
{
    int n;

    while (n = getNum())
    {
        for (int i = 0; i < n; i++)
            num[i] = getNum();
        long long ans = 0;
        merge_sort(0, n - 1, ans);
        printf("%lld\n", ans);
    }

    return 0;
}
inline int getNum()
{
    char c;
    int n = 0;
    while ((c = getchar()) != '\n')
        n = n * 10 + c - '0';
    return n;
}
void merge_sort(int left, int right, long long& swap)
{
    static int sortArr[N];
    if (left == right)
        return;

    int mid = (left + right) >> 1;
    int s1 = left, end1 = mid;
    int s2 = mid + 1, end2 = right;
    merge_sort(s1, end1, swap);
    merge_sort(s2, end2, swap);

    int idx = left;
    while (s1 <= end1&&s2 <= end2)
    {
        if (num[s1] <= num[s2])
            sortArr[idx++] = num[s1++];
        else
        {
            sortArr[idx++] = num[s2++];
            swap += end1 - s1 + 1;//次數為左子序列剩下的還沒排序的數字
        }
    }
    while (s1 <= end1)
        sortArr[idx++] = num[s1++];
    while (s2 <= end2)
        sortArr[idx++] = num[s2++];
    
    //把排序好的數字 assign 回去
    for (int i = left; i <= right; i++)
        num[i] = sortArr[i];
}