Thread: Book Sorting Problem - Help

  1. #1
    Registered User
    Join Date
    Nov 2010

    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.


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

    Sample Input

    2 1 4 5 3

    Sample Output


    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.
    #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++)
    Thank you

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    Right in the middle, where you're doing the actual swapping.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Your bubble sort is not the answer, however.

    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.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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 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.
    Last edited by iMalc; 11-20-2010 at 01:28 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Book problem (split)
    By Rose2502 in forum C Programming
    Replies: 1
    Last Post: 11-16-2010, 11:27 AM
  2. problem sorting a dynamic list
    By andryjohn in forum C Programming
    Replies: 12
    Last Post: 09-05-2009, 12:27 PM
  3. Replies: 26
    Last Post: 06-11-2009, 11:27 AM
  4. Problem with sorting
    By preeengles in forum C Programming
    Replies: 35
    Last Post: 04-22-2009, 07:45 PM
  5. Problem with malloc() and sorting words from text file
    By goron350 in forum C Programming
    Replies: 11
    Last Post: 11-30-2004, 10:01 AM