# UVA Problem 299 – Train Swapping Solution

UVA Problem 299 – Train Swapping Solution:

Solving Technique:

The problem specifically asks to “find the least number of swaps of two adjacent carriages necessary to order the train”. That’s it.

It is a sorting problem and we have to count the number of swap between adjacent carriages. So a stable must be applied. Here I have provided three codes with insertion sort, bubble sort, merge sort.

Even though merge sort is O(n lg n) because input size is so small ( 0 <= L <= 50 ) it doesn’t make much difference. For Bubble sort though no need to perform swaps 🙂 just count it. A hybrid between insertion and merge sort me be a slight performance booster. I will try to include it later.

The problem UVA 11462 age sort is solved also with merge sort among other sort algorithms. A commented version merge sort can be found there.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```3
3
1 3 2
4
4 3 2 1
2
2 1```

Output:

```Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.```

### Code ( Bubble Sort No Swap ):

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 299 Train Swapping (Bubble Sort No Swap)
*/

#include<stdio.h>

/**
* c is swap count
*/
static int A, c;

int main(){
int n, i, j, m;
scanf("%d", &n);

while(n--){
scanf("%d", &m);
for(i = c = 0; i < m; ++i)
scanf("%d", &A[i]);

/**
* Bubble Sort
*/
for(i = 0; i < m - 1; ++i){
for(j = i + 1; j < m; ++j){
/**
* No need to swap elements
* This code may be moved input loop
*/
if(A[i] > A[j])
++c;
}
}

printf("Optimal train swapping takes %d swaps.\n", c);
}
return 0;
}
```

### Code ( Insertion Sort ):

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 299 Train Swapping (Insertion Sort)
*/

#include<stdio.h>

static int A, c;

int main(){
register int n, i, j;
int m, key;
scanf("%d", &n);
while(n--){
scanf("%d", &m);
for(i = c = 0; i < m; ++i)
scanf("%d", &A[i]);

/**
* Insertion sort using inner for loop
*/
for(i = 1; i < m; ++i){
key = A[i];
for(j = i - 1; j >= 0 && A[j] > key; --j){
A[j + 1] = A[j];
++c;
}
A[j + 1] = key;
}

printf("Optimal train swapping takes %d swaps.\n", c);
}
return 0;
}
```

### Code ( Merge Sort Swap Count ):

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 299 Train Swapping (Merge Sort)
*/

#include<stdio.h>
#include<limits.h>

static int A, c;

void Merge(int front, int mid, int rear){
int n1 = mid-front+1;
int n2 = rear - mid;

int *L = new int[n1 + 1];
int *R = new int[n2 + 1];

register unsigned i = 0;
for(; i < n1; ++i)
L[i] = A[front + i];

register unsigned j = 0;
for(; j < n2; ++j)
R[j] = A[mid + 1 + j];

L[n1] = INT_MAX;
R[n2] = INT_MAX;
i = j = 0;

/**
* Might work without swaps by just incrementing index counters
*/
register unsigned k = front;
for(; k <= rear; ++k){
if(L[i] <= R[j]){
A[k] = L[i++];
c += j;
}
else
A[k] = R[j++];
}
}

void Mergesort(int front, int rear){
if(front < rear){
int mid = (rear + front) >> 1;
Mergesort(front, mid);
Mergesort(mid + 1, rear);
Merge(front, mid, rear);
}
}

int main(){
int n, i, j, m;
scanf("%d", &n);
while(n--){
scanf("%d", &m);
for(i = c = 0; i < m; ++i)
scanf("%d", &A[i]);

/**
* To understand Merge sort see my UVA solution age sort 11462
*/
Mergesort(0, m - 1);

printf("Optimal train swapping takes %d swaps.\n", c);
}
return 0;
}
```