Results 1 to 3 of 3
Thread: recursive question
 10122013, 07: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, 08:40 AM #2
 10122013, 09:32 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,288
 Blog Entries
 7
 Rep Power
 24
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,
JosThe only person who got everything done by Friday was Robinson Crusoe.
Similar Threads

Recursive and NonRecursive powersets?
By csisdifficult in forum New To JavaReplies: 5Last Post: 04202011, 02:45 AM 
Recursive Method
By emschorsch in forum New To JavaReplies: 11Last Post: 04182011, 06: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