Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: counting number of comparisons in merge sort

  1. #1
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default counting number of comparisons in merge sort

    guys, I have the following merge sort algorithm, and I'm trying to count the number of comparison that is has to do in order to sort the whole array. I know the formula, I just don't know where to put the counter since it is a recursive algorithm... could someone shed some light on this. Thanks

    //sorting array using merge sort
        static void mergeSort(int[] a)
        {
            if(a.length > 2)
            {
                int mid = a.length / 2;
                int[] first = new int[mid];
                int[] second = new int[a.length - mid];
     
                for(int i = 0; i < first.length; i++) { first[i] = a[i]; }
                for(int i = 0; i < second.length; i++)
                {
                    second[i] = a[mid+i];
                }
                mergeSort(first);
                mergeSort(second);
                merge(first, second, a);
            }
        }
     
        //merging first and second halfs of mergeSort array
        static void merge(int[] first, int[] second, int[] a)
        {
            int iFirst = 0;
            int iSecond = 0;
            int i = 0; 
            //moving the smaller element into a
            while(iFirst < first.length && iSecond < second.length)
            {
                if(first[iFirst] < second[iSecond])
                {
                    a[i] = first[iFirst];
                    iFirst++;
                }
                else
                {
                    a[i] = second[iSecond];
                    iSecond++;
                } 
                i++;
                mergeCounter += i;
            }
            //copying the remaning of the first array
            while(iFirst < first.length)
            {
                a[i] = first[iFirst];
                iFirst++; i++;
            }
            //copying the remaining of second array
            while(iSecond < second.length)
            {
                a[i] = second[iSecond];
                iSecond++; i++;
            }        
        }


  2. #2
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: counting number of comparisons in merge sort

    Hello mia_tech!
    If I'm getting it right you are trying to count how many times executes the first while loop of merge. If you want to count it every time that merge is called you can have a local variable inside the method that does this. For example
    static void merge(int[] first, int[] second, int[] a){       
            int mergeCounter = 0;
     
            while(...){          
                i++;          
            }
            mergeCounter += i; //you have to increment the variable AFTER the loop has exit 
    }
    If you want to count it in a whole mergesort proccess then you should declare mergeCounter as a global variable. For example
     
    class MergeSort{
     
       static int mergeCounter = 0;
     
       static void mergeSort(int[] a){
     
       }
     
       static void merge(int[] first, int[] second, int[] a){      
            while(...){        
                i++;         
            }
            mergeCounter += i; //you have to increment the variable AFTER the loop has exit           
       }
    }
    Hope this helps.

  3. #3
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    yeah, that's exactly what I did... well, kind of, my mergeSorter is inside the while loop, in other words everytime loops is comparing, but yours is outsid the while loop, which gives a different number. Lets take for example an array of 10 numbers with merge sort according to your example it takes 12 comparisons, but if you do it like my code which is inside the while loop it takes 26 comparisons
    Last edited by mia_tech; May 26th, 2012 at 12:56 PM.

  4. #4
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: counting number of comparisons in merge sort

    Cannot test the code right now but I think the problem with your code is that you add i to the counter in every iteration. See the following example:
    1st iteration: i = 1 , counter = 1;
    2nd iteration: i = 2 , counter = 3 (1+2)
    3rd iteration: i = 3 , counter = 6 (3+3).
    So, in three iterations (which is what you want to count) the counter is six when actually the comparisons are 3.
    The actual number of the comparisons is i. Therefore you should add i after the loop (when it has its last value).
    Hope I was clear.

  5. #5
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    Quote Originally Posted by andreas90 View Post
    Cannot test the code right now but I think the problem with your code is that you add i to the counter in every iteration. See the following example:
    1st iteration: i = 1 , counter = 1;
    2nd iteration: i = 2 , counter = 3 (1+2)
    3rd iteration: i = 3 , counter = 6 (3+3).
    So, in three iterations (which is what you want to count) the counter is six when actually the comparisons are 3.
    The actual number of the comparisons is i. Therefore you should add i after the loop (when it has its last value).
    Hope I was clear.
    if you take a look at mergeSort method it has two recursive calls in it, so every time merge is called it reset i = 0, so you need some sort of class variable to keep track of total i's

  6. #6
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: counting number of comparisons in merge sort

    Quote Originally Posted by mia_tech View Post
    if you take a look at mergeSort method it has two recursive calls in it, so every time merge is called it reset i = 0, so you need some sort of class variable to keep track of total i's
    Exactly, this is what I suggested you with the second code of post#2. Did you try it?
    In post#4 I only explained why you need to put the mergeCounter += i; statement after the while loop and not inside it.

  7. #7
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    I think you might be right ;0)

  8. #8
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    so, how many comparison does it take using merge sort to sort an array of 10 numbers?... I got 26, what do you get?
    by doing like you told me gives me only 12 comparison, and I know is more than that, something is wrong....
    Last edited by mia_tech; May 26th, 2012 at 07:03 PM.

  9. #9
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    ok, I forgot that 25 is worst case scenario in which you need to compare all numbers, but here are the numbers I'm comparing. could you tell me what's the number of comparison you get

    45 62 98 89 47 59 72 82 45 18

    Thanks

  10. #10
    Member
    Join Date
    Mar 2009
    Posts
    91
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: counting number of comparisons in merge sort

    Quote Originally Posted by mia_tech View Post
    ok, I forgot that 25 is worst case scenario in which you need to compare all numbers, but here are the numbers I'm comparing. could you tell me what's the number of comparison you get

    45 62 98 89 47 59 72 82 45 18

    Thanks
    the answer is 23 for this array

Similar Threads

  1. Reading text file and counting the number of words, integers, and floats.
    By Jsmooth in forum File I/O & Other I/O Streams
    Replies: 11
    Last Post: April 12th, 2012, 06:39 PM
  2. Counting basic operations in this Selection Sort
    By Keiran in forum Algorithms & Recursion
    Replies: 2
    Last Post: February 1st, 2012, 07:16 PM
  3. Replies: 0
    Last Post: November 6th, 2011, 03:55 PM
  4. Merge sort not sorting at all despite copying it exact from book.
    By javapenguin in forum Other Programming Languages
    Replies: 1
    Last Post: November 1st, 2011, 04:31 PM
  5. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM

Tags for this Thread