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 7 of 7

Thread: displaying every 1000 comparisons in merge sort

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

    Default displaying every 1000 comparisons in merge sort

    gusy, I have the following merge sort algorithm, and if the number of comparisons is over 1000, I need to display every 1000th comparison, but in this case is kind of tricky since the merge sort is recursive... could anyone give me a hand on how to implement this... here's the code

    //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++;             
            }
            counter += i;        
     
            //copying the remaining of 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
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: displaying every 1000 comparisons in merge sort

    Can you show where in the code you are trying to display something?
    How are you trying to detect the 1000th event?
    If you don't understand my answer, don't ignore it, ask a question.

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

    Default Re: displaying every 1000 comparisons in merge sort

    Quote Originally Posted by Norm View Post
    Can you show where in the code you are trying to display something?
    How are you trying to detect the 1000th event?
    I was thinking to implement a if statement right after counter that output to screen in increments of 1000, but it is not working, it outputs wired numbers, besides what if total comparisons are smaller than 1000.

    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++;             
            }
            counter += i;  
            if(counter >= 1000 && counter % 1000 == 0)
                System.out.println(counter);
     
            //copying the remaining of 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++;
            }        
        }

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

    Default Re: displaying every 1000 comparisons in merge sort

    ok, I got it.... is working now, but I have one more question, if I need to display the same for both selection sort and merge sort, wouldn't be better to create a method for that?

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: displaying every 1000 comparisons in merge sort

    What would the method do? Test a value and print a message?
    If you don't understand my answer, don't ignore it, ask a question.

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

    Default Re: displaying every 1000 comparisons in merge sort

    Quote Originally Posted by Norm View Post
    What would the method do? Test a value and print a message?
    test whether the number of comparison is over 1000, if it is then print every 1000th number, and then print the total number of comparisons

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: displaying every 1000 comparisons in merge sort

    Not much more than the if statement you are currently using.
    If you don't understand my answer, don't ignore it, ask a question.

  8. The Following User Says Thank You to Norm For This Useful Post:

    mia_tech (May 28th, 2012)

Similar Threads

  1. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 26th, 2012, 11:54 PM
  2. Replies: 0
    Last Post: November 6th, 2011, 02:55 PM
  3. Win 1000$ now [Java WebApp]
    By biz in forum Paid Java Projects
    Replies: 3
    Last Post: November 2nd, 2011, 11:05 AM
  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. The sum and product of a positive number between 1000 and 9999.
    By metaleddie13 in forum Member Introductions
    Replies: 1
    Last Post: September 15th, 2011, 04:39 AM