Quicksort: Iterative or Recursive

Question

I learnt about quicksort and how it can be implemented in both Recursive and Iterative method.

In Iterative method:

0. Push the range (0...n) into the stack
1. Partition the given array with a pivot
2. Pop the top element.
3. Push the partitions (index range) onto a stack if the range has more than one element
4. Do the above 3 steps, till the stack is empty

And the recursive version is the normal one defined in wiki.

I learnt that recursive algorithms are always slower than their iterative counterpart.

So, Which method is preferred in terms of time complexity (memory is not a concern)?
Which one is fast enough to use in Programming contest?
Is C++ STL sort() using a recursive approach?

Answer 1

So, which method is preferred ...?

Neither, i.e. both at the same time. Modifying the recursiveQsort function from amit's answer, it is

public static void recIterQsort(int[] arr, int start, int end) { 
    while (end - start >= 2) {  // iteratively,
      int p = start + ((end-start)/2);
      p = partition(arr,p,start,end);
      if( p-start < end-p)   // sort shorter part, recursively
      {
          recIterQsort(arr, start, p);
          start = p+1;    // "call" recIterQsort(arr, p+1, end);
      }
      else
      {
          recIterQsort(arr, p+1, end);
          end = p;        // "call" recIterQsort(arr, start, p);
      }
    }
}

Sorting one part recursively, we go on to sort the remaining part in a loop. This transformation is equivalent to performing the tail call optimization, eliminating the recursive call which is the very last operation in a recursive function.

Sorting the shorter part first, the depth of the recursion is guaranteed to be no bigger than log(n), so recursion is not a problem. And the iteration does not have to do any bookkeeping manually with no Stack, so can just use int indices.

Answer 2

That's the solution i came up with in Javascript. I think it works.

const myArr = [33, 103, 3, 726, 200, 984, 198, 764, 9]

document.write('initial order :', JSON.stringify(myArr), '<br><br>')
qs_iter(myArr)
document.write('_Final order :', JSON.stringify(myArr))

function qs_iter(items) {
  if (!items || items.length <= 1) {
    return items
  }
  var stack = []
  var low   = 0
  var high  = items.length - 1
  stack.push([low, high])
  while (stack.length) {
    var range = stack.pop()
    low       = range[0]
    high      = range[1]
    if (low < high) {
      var pivot = Math.floor((low + high) / 2)
      stack.push([low, pivot])
      stack.push([pivot + 1, high])
      while (low < high) {
        while (low < pivot && items[low] <= items[pivot])   low++
        while (high > pivot && items[high] > items[pivot])  high--
        if (low < high) {
          var tmp     = items[low]
          items[low]  = items[high]
          items[high] = tmp
        }
      }
    }
  }
  return items
}

Let me know if you found a mistake :)

Mister Jojo UPDATE :
this code just mixes values that can in rare cases lead to a sort, in other words never. For those who have a doubt, I put it in snippet.

Answer 3

In terms of (asymptotic) time complexity - they are both the same.

"Recursive is slower then iterative" - the rational behind this statement is because of the overhead of the recursive stack (saving and restoring the environment between calls).
However -these are constant number of ops, while not changing the number of "iterations".

Both recursive and iterative quicksort are O(nlogn) average case and O(n^2) worst case.

---

EDIT:

just for the fun of it I ran a benchmark with the (java) code attached to the post , and then I ran wilcoxon statistic test, to check what is the probability that the running times are indeed distinct

The results may be conclusive (P_VALUE=2.6e-34, https://en.wikipedia.org/wiki/P-value. Remember that the P_VALUE is P(T >= t | H) where T is the test statistic and H is the null hypothesis). But the answer is not what you expected.
The average of the iterative solution was 408.86 ms while of recursive was 236.81 ms

(Note - I used Integer and not int as argument to recursiveQsort() - otherwise the recursive would have achieved much better, because it doesn't have to box a lot of integers, which is also time consuming - I did it because the iterative solution has no choice but doing so.

Thus - your assumption is not true, the recursive solution is faster (for my machine and java for the very least) than the iterative one with P_VALUE=2.6e-34.

public static void recursiveQsort(int[] arr,Integer start, Integer end) { 
    if (end - start < 2) return; //stop clause
    int p = start + ((end-start)/2);
    p = partition(arr,p,start,end);
    recursiveQsort(arr, start, p);
    recursiveQsort(arr, p+1, end);

}

public static void iterativeQsort(int[] arr) { 
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(arr.length);
    while (!stack.isEmpty()) {
        int end = stack.pop();
        int start = stack.pop();
        if (end - start < 2) continue;
        int p = start + ((end-start)/2);
        p = partition(arr,p,start,end);

        stack.push(p+1);
        stack.push(end);

        stack.push(start);
        stack.push(p);

    }
}

private static int partition(int[] arr, int p, int start, int end) {
    int l = start;
    int h = end - 2;
    int piv = arr[p];
    swap(arr,p,end-1);

    while (l < h) {
        if (arr[l] < piv) {
            l++;
        } else if (arr[h] >= piv) { 
            h--;
        } else { 
            swap(arr,l,h);
        }
    }
    int idx = h;
    if (arr[h] < piv) idx++;
    swap(arr,end-1,idx);
    return idx;
}
private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void main(String... args) throws Exception {
    Random r = new Random(1);
    int SIZE = 1000000;
    int N = 100;
    int[] arr = new int[SIZE];
    int[] millisRecursive = new int[N];
    int[] millisIterative = new int[N];
    for (int t = 0; t < N; t++) { 
        for (int i = 0; i < SIZE; i++) { 
            arr[i] = r.nextInt(SIZE);
        }
        int[] tempArr = Arrays.copyOf(arr, arr.length);
        
        long start = System.currentTimeMillis();
        iterativeQsort(tempArr);
        millisIterative[t] = (int)(System.currentTimeMillis()-start);
        
        tempArr = Arrays.copyOf(arr, arr.length);
        
        start = System.currentTimeMillis();
        recursvieQsort(tempArr,0,arr.length);
        millisRecursive[t] = (int)(System.currentTimeMillis()-start);
    }
    int sum = 0;
    for (int x : millisRecursive) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);
    sum = 0;
    for (int x : millisIterative) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length);
}

Answer 4

Recursion is NOT always slower than iteration. Quicksort is perfect example of it. The only way to do this in iterate way is create stack structure. So in other way do the same that the compiler do if we use recursion, and propably you will do this worse than compiler. Also there will be more jumps if you don't use recursion (to pop and push values to stack).