**UVA Problem 299 – Train Swapping Solution:**

Click here to go to this problem in uva Online Judge.

**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 ) * @link https://quickgrid.wordpress.com * Problem: UVA 299 Train Swapping (Bubble Sort No Swap) */ #include<stdio.h> /** * c is swap count */ static int A[64], 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 ) * @link https://quickgrid.wordpress.com * Problem: UVA 299 Train Swapping (Insertion Sort) */ #include<stdio.h> static int A[64], 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 ) * @link https://quickgrid.wordpress.com * Problem: UVA 299 Train Swapping (Merge Sort) */ #include<stdio.h> #include<limits.h> static int A[64], 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; }