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

Thread: Help with using mergesort to sort a list of names alphabetically?

  1. #1
    Junior Member
    Join Date
    Mar 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Help with using mergesort to sort a list of names alphabetically?

    Hi, I'm trying to sort a list of names alphabetically, case-insensitive by using the mergesort technique.
    I wrote this code and when I trace it through on paper with an example array of names, it should work, but when I run it with an actual txt file, it's not correctly alphabetical.
    I'd appreciate it if someone could take a look at my code and give me some ideas on what my problem might be.
    Thanks in advance! (note: I also posted this question to java-forums.org and coderranch.org, as I've been working on this little problem for over five hours and am in desperate need of some help!)

    public static void mergeSort(String[] names)  
        {  
            if (names.length >= 2)  
            {  
                String[] left = new String[names.length/2];  
                String[] right = new String[names.length-names.length/2];  
     
                for (int i = 0; i < left.length; i++)  
                {  
                    left[i] = names[i];  
                }  
                for (int i = 0; i < right.length; i++)  
                {     
                    right[i] = names[i + names.length/2];  
                }  
     
                mergeSort(left);  
                mergeSort(right);  
                merge(names, left, right);  
            }  
        }  
     
       // pre : result is empty; list1 is sorted; list2 is sorted  
       // post: result contains result of merging sorted lists;  
       // add merge method below  
     
        public static void merge(String[] names, String[] left, String[] right)  
        {  
            int i1 = 0;  
            int i2 = 0;  
     
            for (int i = 0; i < names.length; i++)  
            {  
                if (i2 >= right.length || (i1 < left.length && left[i1].compareToIgnoreCase(right[i1])<0))  
                {  
                    names[i] = left[i1];  
                    i1++;  
                } else  
                {  
                    names[i] = right[i2];  
                    i2++;                 
                }  
            }  
        }     
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,585
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    Can you post the contents of the list before the sort and after the sort so we can see what the code does?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,387
    My Mood
    Hungover
    Thanks
    144
    Thanked 628 Times in 538 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    Have you stepped through this with a debugger, or at least added some print statements, to figure out the flow of the program?

    And would you mind linking to those other posts? For all we know, this was answered hours ago...
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  4. #4
    Junior Member
    Join Date
    Mar 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    Quote Originally Posted by Norm View Post
    Can you post the contents of the list before the sort and after the sort so we can see what the code does?
    Hi, yes, I created a "test" file, since the original file was too large to look at carefully.

    The list would make a array {M, B, J, A, Z, C} without sorting

    After being merge sorted, the array should look like {A, B, C, J, M, Z}, but instead it looks like {A, C, Z, B, J, M}

    I've gone through the code step by step countless times and I can't seem to figure out what's wrong.

    Thanks for any help!

  5. #5
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,387
    My Mood
    Hungover
    Thanks
    144
    Thanked 628 Times in 538 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    And when you stepped through the code, at what point does the code behave differently from what you'd expect?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  6. #6
    Junior Member
    Join Date
    Mar 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    That's what's confusing me, I traced the whole thing with that test run on paper, and I get the output I'm shooting for.
    But not when I compile and run it. Please help!!

  7. #7
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,387
    My Mood
    Hungover
    Thanks
    144
    Thanked 628 Times in 538 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    Right. That's why I'm asking you to step through the actual code with a debugger or even some print statements to figure out when the actual program differs from what you expect on paper and pencil. You're asking us to debug your program for you. I'm trying to get you to debug it yourself. Teach a man to fish, and all that.

    Recommended reading: http://www.javaprogrammingforums.com...t-println.html
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,585
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: Help with using mergesort to sort a list of names alphabetically?

    Try a simple input of Strings in reverse order so you can easily see what is happen at each step.
    {"Z","Y","X","W","V", "U"}

    I suspect you will get something like: {X, Y, Z, U ,V , W}
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. [SOLVED] Linked List (adding alphabetically)
    By Usoda in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 11th, 2012, 12:17 PM
  2. [SOLVED] Sorting strings alphabetically
    By userct in forum What's Wrong With My Code?
    Replies: 0
    Last Post: February 21st, 2012, 03:38 PM
  3. How to sort alphabetically?
    By colerelm in forum Java Theory & Questions
    Replies: 2
    Last Post: December 4th, 2011, 10:59 AM
  4. Insertion Sort on a Doubly Linked List
    By Kaisshau in forum What's Wrong With My Code?
    Replies: 4
    Last Post: June 7th, 2011, 11:18 PM
  5. Pseudo code of insertion sort linked list
    By sungirl in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 23rd, 2010, 09:25 AM