UVa_10810_Ultra-QuickSort.cpp

Problem Links:

poj2299, uva10810,

Problem:

Problem B: Ultra-QuickSort

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Output for Sample Input

6
0

---

Stefan B�ttcher

Solution:

Source Code:

//Thu Apr 14 14:19:42 CDT 2011
#include<stdio.h>
#include <iostream>
using namespace std;
#define MAX 500001
long long MergeSort(long a[], long c[], int left, int right) {
    int i, j, mid, temp, count;
    long long total = 0;
    if (right > left) {
        mid = (left + right) / 2;
        total += MergeSort(a, c, left, mid);
        total += MergeSort(a, c, mid + 1, right);
        count = 0;
        for (i = left, j = mid + 1; i <= mid && j <= right;) {
            if (a[i] > a[j]) {
                total += mid - i + 1;
                c[++count] = a[j++];
            } else
                c[++count] = a[i++];
        }
        while (i <= mid)
            c[++count] = a[i++];
        while (j <= right)
            c[++count] = a[j++];
        for (i = left; i <= right; i++)
            a[i] = c[i - left + 1];
    }
    return total;
}
long a[MAX], c[MAX];
int main(void) {
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    long n;
    int i, j;
    long long total;
    scanf("%ld", &n);
    while (n != 0) {
        for (i = 1; i <= n; i++)
            scanf("%ld", &a[i]);
        total = MergeSort(a, c, 1, n);
        cout << total << endl;
        scanf("%ld", &n);

    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}