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.
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.
A single integer indicating the minimum number of moves necessary to sort Indraneel's book-shelf.
You may assume that 1 ≤ N ≤ 200000. You may also assume that in 50% of the inputs, 1 ≤ N ≤ 5000.
Here is the sample input and output corresponding to the example discussed above.
2 1 4 5 3
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.
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;
for(i=1; i <= N-1; i++)
for(i=0; i<=N-1; i++)