0

In the code listed below I am trying to figure out how to turn it into a iterative solution. I understand the concept of recursion but I am trying to develop a quick-sort program and also want to show the iterative process. 

public void recursiveSort(int lowerIndex, int higherIndex) {
    int i = lowerIndex;
    int j = higherIndex;
    // calculate pivot number, I am taking pivot as middle index number
    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    // Divide into two arrays
    while (i <= j) {

        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchangeNumbers(i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j){
        recursiveSort(lowerIndex, j);
    }
    if (i < higherIndex){
        recursiveSort(i, higherIndex);
    }
}

The part that I am trying to modify is....

    // call recursiveSort() method recursively
    if (lowerIndex < j){
        recursiveSort(lowerIndex, j);
    }
    if (i < higherIndex){
        recursiveSort(i, higherIndex);
    }

Thanks for any help offered!!

James Lockhart
  • 131
  • 1
  • 2
  • 11
  • 3
    Possible duplicate of [Way to go from recursion to iteration](http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) – sidgate Sep 13 '16 at 20:42
  • it's not clear how this is iterating over anything. it looks like it's taking two numbers, not an array. might be helpful to show a fiddle of how it works. – Robert Parham Sep 13 '16 at 20:47
  • Note that if you put everything from `int pivot = ...` through the end of the method into a loop, then you can convert one of the two recursive calls into an iterative one almost for free. Instead of recursing, just set new starting values for `i` and `j` and loop back to the top. In fact, if you take care always to do this for the larger partition, then you can put a firm upper bound on the size of the stack you will need to flatten the other recursive call. This technique can be used in (half-)recursive quicksorts, too, to place a bound on recursion depth. – John Bollinger Sep 13 '16 at 20:55

0 Answers0