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 me, java quicksort!

  1. #1
    Junior Member
    Join Date
    Jan 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Help me, java quicksort!

    Hello, I got a problem that I just can't solve.. The program is supposed to sort the random int-array with a "quickSort". But I dont get it to work, I do get a list of 20 int's and they're almost sorted. But it's almost always a few int's on the wrong place. What have I done wrong? Would really appreciate help! :)
    Sorry if it looks messy.

    import java.util.Random;
     
    public class quickSorterARN {
     
    	public static void main (String[] args) {
    		Random rand = new Random();
    		int a[] = new int[20];
    		for (int i = 0; i < a.length; ++i) {
    			a[i] = rand.nextInt(100);
    		}
    		quickSorter(a, 0, a.length - 1);
    		for (int i = 0; i < a.length; ++i) {
    			System.out.println(a[i]);
    		}
    	}
     
    	static void quickSorter(int[] data, int first, int last) {
    		int top = first;
    		int bot = last;
     
    		int midValue = data[(top+bot)/2];
    		while (top < bot) {
    			for (; data[top] < midValue; ++top)
    				;
    			for (; data[bot] > midValue; --bot)
    				;
     
    			if (top <= bot) {
    				int temp = data[top];
    				data[top] = data[bot];
    				data[bot] = temp;
    				++top;
    				--bot;
    			}
    		}
    		if (top < last && bot > first) {
    			quickSorter(data, first, bot);
    			quickSorter(data, top, last);
     
    		}
    	}
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,139
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default Re: Help me, java quicksort!

    Some suggestions:
    Use the Arrays class's toString() method to format the array for printing.
          System.out.println("Before="+java.util.Arrays.toString(a));  // show before sort
    Print the array before and after the sort to see what the input was.
    When you find an array's contents that is sorted incorrectly, copy the print out and use it to initialize the array so the data will always be the same for testing. Remove any duplicates so all elements are unique.

    Then when you are trying to debug the code with println statements (or break points) the data being sorted will always be the same which will make it easier to find the problem.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Help me, java quicksort!

    Quote Originally Posted by Joeyeyey View Post
    ... problem...
    I don't understand this at all:
     
            if (top < last && bot > first) {
                quickSorter(data, first, bot);
                quickSorter(data, top, last);
            }

    I'm not too nuts about your choice of names of variables, but it seems to me that if top is less than last, you need to call the function recursively to sort that part, regardless of the other part.

    Similarly, if first is less than bot, you need to sort that part, regardless of the other part, don't you?

    Are you working from pseudo-code? What is your reference?


    Cheers!

    Z

  4. #4
    Junior Member
    Join Date
    Jan 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help me, java quicksort!

    Okay, will try that. Thanks!

    --- Update ---

    Quote Originally Posted by Zaphod_b View Post
    I don't understand this at all:
     
            if (top < last && bot > first) {
                quickSorter(data, first, bot);
                quickSorter(data, top, last);
            }

    I'm not too nuts about your choice of names of variables, but it seems to me that if top is less than last, you need to call the function recursively to sort that part, regardless of the other part.

    Similarly, if first is less than bot, you need to sort that part, regardless of the other part, don't you?

    Are you working from pseudo-code? What is your reference?


    Cheers!

    Z

    Well, I have tried this if this is what you mean:
    if (top < last)
            quickSorter(data, first, bot);
    if (bot > first)
    	quickSorter(data, top, last);

    But it didn't work either :/

    Im just learning Java on my own at home, this is just a practicequestion in the book.

    --- Update ---

    Hmm, well. You were right, I changed it from "top < last && bot > first" to "top < last || bot > first".
    But in the book they used "&&", in exactly the same situation. But can you please explain to me as if I were 5 years old. Why this didnt work with "&&"?
    Thanks alot for the help both of you!

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,139
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default Re: Help me, java quicksort!

    Are you working from pseudo-code? What is your reference?
    As Zaphod_b asked above, do you have an algorithm for what you are trying to do?
    Add the algorithm as comments in the code and try to write code to follow it.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #6
    Junior Member
    Join Date
    Jan 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help me, java quicksort!

    Quote Originally Posted by Norm View Post
    As Zaphod_b asked above, do you have an algorithm for what you are trying to do?
    Add the algorithm as comments in the code and try to write code to follow it.
    It's just a simple question in the book, Im supposed to implement quickSort instead of bubbleSort. (I learned earlier in the book how to implement bubbleSort.) There is no algorithm.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,139
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default Re: Help me, java quicksort!

    There is no algorithm.
    There must be. You can NOT write a program with any complexity without having designed it and in the process created the algorithm for solving the problem. You can not write a sort program by typing in random statements.
    If you don't understand my answer, don't ignore it, ask a question.

  8. #8
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Help me, java quicksort!

    Quote Originally Posted by Joeyeyey View Post
    Well, I have tried this...
    if (top < last)
            quickSorter(data, first, bot);
    if (bot > first)
    	quickSorter(data, top, last);

    But it didn't work
    ...
    But that didn't do what I hinted at.

    I hate to repeat myself, but
    Quote Originally Posted by Zaphod_b (emphasis added)
    if top is less than last, you need to call the function recursively to sort that part.

    if first is less than bot, you need to sort that part.
    Bottom line: I wouldn't have made my suggestion unless I had tested it.

    Quote Originally Posted by Joeyeyey View Post
    But in the book they used "&&", in exactly the same situation.
    I asked what reference you were using. I meant, what reference for quicksort. What is the name of the book or other source of your idea for quicksort? Are you saying that the book had an example of quicksort that is exactly like your code and that it used && in code or pseudocode for quicksort the way you did? (I'm not sure what you mean by "exactly the same situation.")


    Quote Originally Posted by Joeyeyey View Post
    I changed it from "top < last && bot > first" to "top < last || bot > first"
    Well, that's not entirely unrelated to what I had in mind, but it doesn't demonstrate (much) understanding of the problem. I am glad you asked for more information.

    Quote Originally Posted by Joeyeyey View Post
    You were right
    I'm not always "right" but I do test my suggestions before posting.

    Quote Originally Posted by Joeyeyey View Post
    ...explain...Why this didnt work with "&&"?
    Well, let's see...

    The problem is that I can't explain why 2*3 is not equal to 5 but 2+3 is equal to 5 in the limited space and bandwidth of this forum and with my space-and-bandwidth-limited brain. I have to say that, in general, it's not always easy to explain why doing the wrong thing gives the wrong answer. Maybe you can explain to me why you think && would work here.

    Anyhow, here is the short form of an implementation rationale...

    The way I see it (in vague generalities) is that the whole point of quicksort is, at each stage, it splits the array into two partitions with certain properties. Certain conditions can cause recursive calls to create smaller and smaller sub-partitions until everything is sorted.


    If the first partition needed further sorting but the second didn't, using the && operator between the conditions would fail and no further sorting would be done. Furthermore (as if a furthermore were really needed), if the second part required sorting but the first part didn't, using the && operator would fail, and no more sorting would be done.

    The fact that your original program sometimes "leaves a few ints in the wrong place" indicates that the result depends on the order of the values in the randomly populated array. Sometimes, it "just happens" that it gets sorted, where with a different ordering it gets "almost" sorted. That means that sometimes it quits too soon rather than doing further recursion.

    On the other hand, using the || operator would result in the both parts being sorted if either one (or both) needed to be sorted. (So it would "work.")

    Code following my suggestion a little more closely might look something like the following, which would sort a sub-partition only if it needed to be sorted. (Naive implementations of quicksort tend to do a lot of extra work on partitions that are already sorted.)

    IF top is less than last THEN
        Call quickSorter on the partition that has top and last
    END IF
     
    IF bot is greater than first THEN
        Call quickSorter on the partition that has first and bot
    END IF



    Cheers!

    Z

Similar Threads

  1. Using Quicksort on a Vector of Integers?
    By mescoff in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 14th, 2012, 08:25 AM
  2. Stackoverflow Recursive quicksort
    By IHeartProgramming in forum Algorithms & Recursion
    Replies: 2
    Last Post: September 23rd, 2012, 01:42 PM
  3. Quicksort
    By wholegrain in forum Java Theory & Questions
    Replies: 7
    Last Post: February 12th, 2012, 08:31 PM
  4. QuickSort method
    By D3158 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 15th, 2011, 09:17 PM
  5. StackOverflowError when using quicksort
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 3
    Last Post: April 22nd, 2011, 05:24 PM