1. Member 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  Reply With Quote

2. ## Re: recursive question Originally Posted by Nhatmeister 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) ?  Reply With Quote

3. ## 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,

Jos  Reply With Quote

#### Posting Permissions

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