Results 1 to 3 of 3
  1. #1
    Nhatmeister is offline Member
    Join Date
    Aug 2013
    Posts
    11
    Rep Power
    0

    Default 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

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default Re: recursive question

    Quote Originally Posted by Nhatmeister View Post
    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) ?
    Sounds about right.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Recursive and Non-Recursive powersets?
    By csisdifficult in forum New To Java
    Replies: 5
    Last Post: 04-20-2011, 03:45 AM
  2. Recursive Method
    By emschorsch in forum New To Java
    Replies: 11
    Last Post: 04-18-2011, 07:01 AM
  3. very frustrating.. recursive
    By Yakg in forum New To Java
    Replies: 5
    Last Post: 01-06-2011, 11:25 PM
  4. basic help with Recursive
    By syntrax in forum New To Java
    Replies: 3
    Last Post: 12-15-2009, 07:19 AM
  5. pleasee help me out for this recursive question!!!
    By javasucks2009 in forum New To Java
    Replies: 3
    Last Post: 03-18-2009, 10:45 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
  •