uva 299 - Train Swapping

 1  /*
 2  Problem link
 3  Type: Ad hoc, Sorting.
 4  Algorithm: Insertion Sort.
 5  */
 6  #include <iostream>
 7  #include <cstdio>
 8  #include <cstring>
 9  #include <cstdlib>
10  using namespace std;
11  
12  const int maxn = 60;
13  
14  int a[maxn];
15  int n;
16  
17  int InsertionSort();
18  
19  int main()
20  {
21      int ntest;
22      cin >> ntest;
23      for (int test=1; test<=ntest; test++)
24      {
25          cin >> n;
26          for (int i=1; i<=n; i++) cin >> a[i];
27          printf("Optimal train swapping takes %d swaps.\n",InsertionSort());
28      }
29      return 0;
30  }
31  
32  int InsertionSort() {
33      int result = 0;
34      for (int i=2; i<=n; i++)
35      {
36          int key = a[i];
37          int j = i-1;
38          while (j>0 && a[j]>key)
39          {
40              a[j+1] = a[j];
41              j--;
42              result++;
43          }
44          a[j+1] = key;
45      }
46      return(result);
47  }