Results 1 to 5 of 5
  1. #1
    hawaiifiver is offline Member
    Join Date
    Jan 2009
    Posts
    21
    Rep Power
    0

    Default Quick Sort explanation.

    Hi guys. I am trying to understand the following code. This isnt an assignment, I am just trying to understand this program. It implements the quick sort method. But I find the code slightly confusing. Could you help me understand it a bit better? Some things I am not clear on:

    1. Why do they have that return statement in the quickSort() method
    2. What are those two inner while loops doing?
    3. What is the code in the brackets doing. quickSort(a, lo == low ? lo+1 : lo, n);

    Thanks.
    Here is the code:

    Java Code:
    class Quick
    
    {
    
    	public static void main(String[] args)
    	{
    
    	int [] a = {3,4,1,2,5, 9, 6};
    	int i;
    	
    
    	quickSort(a, 0, a.length - 1);
    
    	for(i = 0; i <a.length; i++)
    	{System.out.println(a[i]);}
    
    	}//main
    
    
    	public static void quickSort(int a[], int low, int n)
    
    	{
    
    
    	int lo = low;
        	int hi = n;
    
    	
        if (lo >= n) {
          			return;
        			}
    
    
    
    
    	int mid = a[(lo + hi)/2];
    
    	while (lo < hi)
    
    	{
    
    	while (lo < hi && a[lo] < mid)
    	{
    		lo ++;
    	
    
    	}//end inner while
    
    	while (lo < hi && a[hi] > mid)
    	{
    
    		hi --;
    	}//end inner while
    
    
    	if (lo < hi)
    	{
    		int temp = a[lo];
    		a[lo] = a[hi];
    		a[hi] = temp;
    
    	}//end if
    
    	}//end outer while
    
    
    	if (hi < lo) {
          			int temp = hi;
          			hi = lo;
          			lo = temp;
        		     }
    
        		quickSort(a, low, lo);
        		quickSort(a, lo == low ? lo+1 : lo, n);
    
    		
    	}//end method
    
    
    	
    
    }//class

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by hawaiifiver View Post
    1. Why do they have that return statement in the quickSort() method
    return statement use simply to exit the code. In this case is used to exit from the method.

    Quote Originally Posted by hawaiifiver View Post
    2. What are those two inner while loops doing?
    Better to take a piece of paper and write the logic on it and see.

    Quote Originally Posted by hawaiifiver View Post
    3. What is the code in the brackets doing. quickSort(a, lo == low ? lo+1 : lo, n);
    This is about ternary operator. Much similar to the if-else condition.

    Java Code:
    lo == low ? lo+1 : lo
    You can right the same logic using if-else as follows.

    Java Code:
    if(lo == low) {
        [I]select [B]lo + 1[/B][/I]
    }
    else {
        [I]select [B]lo[/B][/I]
    }

  3. #3
    hawaiifiver is offline Member
    Join Date
    Jan 2009
    Posts
    21
    Rep Power
    0

    Default

    ah cool. i thought those inner while loops were searching the array.

  4. #4
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    a better thing to do would be search out pseudocode for quick sort (i'd imagine wikipedia would have some) and then compare them. while it can be a good trait to be able to read code and decipher what it's doing, a more descriptive version might be more useful to you.

    funny, i tried googling and everything is rejected as 'looking similar to automated requests from a virus'.

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

Similar Threads

  1. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  2. Quick sort with median-of-three partitioning
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:40 PM
  3. Simple version of quick sort
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:40 PM
  4. Class explanation
    By mcal in forum New To Java
    Replies: 1
    Last Post: 02-05-2008, 06:50 PM
  5. need a little explanation
    By cew27 in forum New To Java
    Replies: 7
    Last Post: 12-13-2007, 11:39 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •