Book Sorting Problem - Help

Hello, I am new to programming and I am preparing for International olympiad in informatics. Hence for that I need some help in some of the problems.
Please help me write the code along with explanation for the following problem:



Problem 1: Book Sorting,
Indraneel has to sort the books in his library. His library has one long shelf. His books are numbered 1 through N and he wants to rearrange the books so that they appear in the sequece 1,2, ..., N.

He intends to do this by a sequence of moves. In each move he can pick up any book from the shelf and insert it at a different place in the shelf. Suppose Indraneel has 5 books and they are initially arranged in the order

2 1 4 5 3

Indraneel will rearrange this in ascending order by first moving book 1 to the beginning of the shelf to get

1 2 4 5 3

Then, moving book 3 to position 3, he gets

1 2 3 4 5

Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his book shelf.

Input format

The first line of the input will contain a single integer N indicating the number of books in Indraneel's library. This is followed by a line containing a permutation of 1, 2, ..., N indicating the intial state of Indraneel's book-shelf.

Output format

A single integer indicating the minimum number of moves necessary to sort Indraneel's book-shelf.

Test Data:

You may assume that 1 ≤ N ≤ 200000. You may also assume that in 50% of the inputs, 1 ≤ N ≤ 5000.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

5
2 1 4 5 3

Sample Output

2

I tried to solve it, here is my source code however I dont know where to place the counter to calculate the no. of moves required.

Code:

---

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int numbers[], int array_size)

{
  int i, j, temp;
 
  for (i = (array_size - 1); i >= 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (numbers[j-1] > numbers[j])
      {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

int main()

{
int M[5000];
int N;
int i;
scanf("%d", &N);
for(i=1; i <= N-1; i++)
{
scanf("%d", &M[i]);
}
bubbleSort(M, N);
for(i=0; i<=N-1; i++)
{
printf("\n%d",M[i]);
}
scanf("%d");
}

---

Thank you

Right in the middle, where you're doing the actual swapping.

Your bubble sort is not the answer, however. :p

The sort you want is Selection sort - it always has the fewest possible moves required.

In fact, that is the REASON for the sort.

There are three main factors for a sorting algorithm:

1) It has low complexity - ie. it is fast!

2) It has a low number of comparisons - maybe even none! If comparisons are "expensive" - maybe the data has to be compared via a remote network.

3) It has a low number of moves.

You can read more about Selection sort on Wikipedia, including pseudo code and links.

Yep, I read the original problem and "Linked-list-based Selection Sort" immediately jumped out at me.

However, they are asking for the minimum number of moves. Using ordinary list based selection sort, the below would result in 4 moves, when clearly it can be done in one, it's just that the one would be a move from left to right, rather than four moves from right to left.

5
5 1 2 3 4
I think one important point is that although a move costs you, the distance it is moved does not.
You could start by finding the longest increasing subsequence, and then strategicaly insert all the rest into it but I don't think that's quite optimal either because there could be just one item splitting a long increasing subsequence in two, which when moved would make it the longest run afterall.
They definitely don't make these olympiad things that easy you know. I gave up on a maths olympiad thing once when I was quite young. Lets just say that if your hardest part is how to count the swaps, then you're probably not going to be solving this any time soon.