299 - Train Swapping

I think this problem is an implementation of the insertion sort algorithm (http://en.wikipedia.org/wiki/Insertion_sort). Given a sequence 4 3 2 1, you can perform swaps on the numbers as follows:

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

This gives a total of 6 swaps. Here's another sequence and the sequence of swaps performed to sort the numbers:

4 3 5 1 2

3 4 5 1 2

3 4 1 5 2

3 1 4 5 2

1 3 4 5 2

1 3 4 2 5

1 3 2 4 5

1 2 3 4 5

This gives a total of 7 swaps.

So, one can simply implement the sequence of swaps and count the swaps.

Here's the code. By the way, I used scanf("%d\n", &n) in this code. I noticed that if I don't put \n in the scanf() function, the code does not accept input properly. The scanf() has to be used with the \n character.

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

int main() {

  char line[1000];

  int n, i, l, j, k, p, swaps, temp;

  int c[100];

  char *pch;

  scanf("%d\n", &n);

  for (i = 0; i < n; i += 1) {

    scanf("%d\n", &l);

    gets(line);

    pch = strtok(line, " \t\n");

    for (j = 0; j < l; j += 1) {

      c[j] = atoi(pch);

      pch = strtok(NULL, " \t\n");

    }

    for (k = 1, swaps = 0; k < l; k += 1) {

      for (p = k - 1; p >= 0; p--) {

        if (c[p] < c[p+1]) {

          break;

        }

        temp = c[p];

        c[p] = c[p+1];

        c[p+1] = temp;

        swaps += 1;

      }

    }

//    printf("B");

//    for (j = 0; j < l; j += 1) {

//      printf("%d ", c[j]);

//    }

//    printf("E\n");

    printf("Optimal train swapping takes %d swaps.\n", swaps);

  }

  return 0;

}