Results 1 to 3 of 3
Thread: recursive question
 10122013, 08:10 AM #1Member
 Join Date
 Aug 2013
 Posts
 11
 Rep Power
 0
recursive question
Hi,
This is part of the QuickSort algorithmn I am trying to understand.
public static void sort(double[] a, int begin, int end){
if((end  begin) >= 1)
{
int splitPoint = split(a, begin, end);
sort(a, begin, splitPoint);
sort(a, splitPoint + 1, end);
}
}
How does the recursive call work in this case ? After getting a return value from split()
Does it execute sort(a, begin, splitPoint) until base case is met, then back track each stack ? then go to sort(a, splitPoint + 1, end) ?
Or does it do sort(a, begin, splitPoint) follow by sort(a, splitPoint + 1, end) until base case is met ?
Thanks
 10122013, 09:40 AM #2
 10122013, 10:32 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: recursive question
A proof 'by intimidation' runs as follows: suppose the sort( ... ) method works; the real 'intelligence' is in the splitPoint( ... ) method, i.e. it has to find an index n such that for all j < n, array[j] <= array[n] and for all j > n, array[j] >= array[n] (iow, elements to the left of n have to be smaller than array[n] and elements to the right of n have to be larger than array[n]). If you sort the elements to the left of n and the elements to the right of n you have sorted the entire array.
An example: array= { 3, 2, 1, 4, 7, 6, 5 } and you pick 4 as the pivot; the elements to the left of 4 are smaller than 4 and all elements to the right of 4 are larger than 4; if you can sort the elements { 3, 2, 1 } and { 7, 6, 5 } you have sorted the entire array.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

Recursive and NonRecursive powersets?
By csisdifficult in forum New To JavaReplies: 5Last Post: 04202011, 03:45 AM 
Recursive Method
By emschorsch in forum New To JavaReplies: 11Last Post: 04182011, 07:01 AM 
very frustrating.. recursive
By Yakg in forum New To JavaReplies: 5Last Post: 01062011, 11:25 PM 
basic help with Recursive
By syntrax in forum New To JavaReplies: 3Last Post: 12152009, 07:19 AM 
pleasee help me out for this recursive question!!!
By javasucks2009 in forum New To JavaReplies: 3Last Post: 03182009, 10:45 PM
Bookmarks