## Thursday, April 14, 2011

### UVa_10810_Ultra-QuickSort.cpp

poj2299, uva10810,

## 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.

```5
9
1
0
5
4
3
1
2
3
0```

```6
0```

Stefan B�ttcher

## 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;
}