Mergesort and couting the amount of inversions

Discussion in 'C++' started by Jochus, Oct 30, 2005.

  1. Jochus

    Jochus Guest

    Today, I've programmed Mergesort. And it works very good :)!

    But now, the teacher said that you could use Mergesort to count the amount
    of inversions.

    This is what I found on the internet:

    ---
    Note: Merge Sort can be slightly modified to count inversion index (i.e.
    bubble sort swaps) in O(n log n) time. When the right partition goes in
    first in Merge step, that means all the remaining items in left partition <
    first element in right partition (i.e. you have to swap with all of them).
    ---

    Can someboy give me some information about that sentence? I don't really
    understand the meaning of it...
    Jochus, Oct 30, 2005
    #1
    1. Advertising

  2. Jochus

    John Ratliff Guest

    Jochus wrote:
    > Today, I've programmed Mergesort. And it works very good :)!
    >
    > But now, the teacher said that you could use Mergesort to count the amount
    > of inversions.
    >
    > This is what I found on the internet:
    >
    > ---
    > Note: Merge Sort can be slightly modified to count inversion index (i.e.
    > bubble sort swaps) in O(n log n) time. When the right partition goes in
    > first in Merge step, that means all the remaining items in left partition <
    > first element in right partition (i.e. you have to swap with all of them).
    > ---
    >
    > Can someboy give me some information about that sentence? I don't really
    > understand the meaning of it...
    >
    >


    This is not a question for comp.lang.c++ which deals with standard C++
    language issues ONLY. Please find a newgrsoup dedicated to algorithms.

    See http://www.parashift.com/c -faq-lite/ for more information.

    --John Ratliff
    John Ratliff, Oct 30, 2005
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jazzy
    Replies:
    3
    Views:
    10,625
    Gordon Beaton
    May 25, 2004
  2. Chris Schumacher

    couting cout.

    Chris Schumacher, Apr 13, 2004, in forum: C++
    Replies:
    1
    Views:
    364
    Buster
    Apr 13, 2004
  3. xandra
    Replies:
    3
    Views:
    277
    Richard Heathfield
    Nov 10, 2006
  4. xandra

    how many inversions????

    xandra, Nov 10, 2006, in forum: C++
    Replies:
    1
    Views:
    328
    Ian Collins
    Nov 10, 2006
  5. Chad
    Replies:
    5
    Views:
    546
Loading...

Share This Page