Quicksort: Iterative or Recursive

Question

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

In Iterative method:

Push the range (0...n) into the stack
Partition the given array with a pivot
Pop the top element.
Push the partitions (index range) onto a stack if the range has more than one element
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?

you have already answered yourself. Recursive version is shorter and more clear. Iterative is faster and makes you simulate the recursion call stack. — Vitaly Olegovitch
– Vitaly Olegovitch, Commented Sep 23, 2012 at 14:44
But my prof told that the recursion stack depth is same as stack which we use for storing partition range. So, how iterative one is significantly faster? — sabari
– sabari, Commented Sep 23, 2012 at 14:46
@sabari: Your assumption about recursive being faster is wrong. I statistically tested these assumptions and editted the answer with the results. — amit
– amit, Commented Sep 24, 2012 at 8:06
You can implement an iterative version of Quicksort with a queue rather than a stack. There's nothing about the algorithm that requires the extra storage to be LIFO. The stack approach is more similar to the recursive description commonly used for Quicksort, but that's not actually an inherent part of the algorithm. It's perhaps likely that a LIFO structure will give better locality of reference, so it may be faster because it's more cache friendly. — Adrian McCarthy
– Adrian McCarthy, Commented Nov 23, 2015 at 23:50
I guess the difference is one of heap vs staxk space. Penalty for garbage collection is high. — Adrian V
– Adrian V, Commented Dec 1, 2016 at 11:34

Avi · Accepted Answer · 2021-01-28 07:24:10Z

28

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);
}

edited Jan 28, 2021 at 7:24

Avi

2,1808 gold badges27 silver badges44 bronze badges

answered Sep 23, 2012 at 14:48

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Argeman Over a year ago

Your test mainly is showing how efficient the Stack class is working, not how efficient the iterative version of quicksort is. You can use more a static, self written stack of for example 64 elements and the push and pop operations will be much faster. I guess that will be faster than the recursive one! And if you implement it the right way, you can sort 2^64 elements in the worst case, which is simply enough in practical applications.

amit Over a year ago

@Argeman: Thanks for your comment. This is actually the point of the benchmark - the stack solution is very dependent on the stack implementation while the call stack is pretty much optimized for its purpose already, and thus a recursive solution is not likely to be worse then an iterative one, unless you spend a lot of time optimizing the stack for specific purpose (and I doubt the difference will be significant enough to worth the time). As I said, it is just a "fun test" - the main idea behind the answer yet remains - the asymptotic time complexity is the same.

amit Over a year ago

P.S. The broken printing format (and not using Arrays.toString()) is to fit the input expected by the wilcoxon online calculator in fon.hum.uva.nl/Service/Statistics/Wilcoxon_Test.html

Geek Over a year ago

@amit how did u run the "Wilcoxon signed-rank test"...Any tool that u have used ?

amit Over a year ago

@Geek: I put the on-line tool I used as a comment (The one starting with P.S). PythonXY also has it implemented as scipy.stats.wilcoxon

|

Hauleth · Accepted Answer · 2012-09-23 14:47:38Z

11

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).

answered Sep 23, 2012 at 14:47

Hauleth

23.7k4 gold badges67 silver badges117 bronze badges

5 Comments

Vitaly Olegovitch Over a year ago

Why do you have to jump in order to pop and push?

Hauleth Over a year ago

If it's not inlined you (in most cases) need to call some functions, so it need to call.

Akash Magoon Over a year ago

Just to confirm, are you saying that using the runtime stack (recursive) is more efficient than a stack structure create by the user? @amit do you have any thoughts?

Hauleth Over a year ago

I think that it is less efficient. Because you need to alloc enough heap to build stack (or even realloc if you run out of free memory), you need to store position somewhere, you need to check against corner cases (empty/full stack), etc.

Hassan Faghihi Over a year ago

at sometime long ago i saw application crash due too many, and compiler limitation of recursion call , is it still the case in new days? what about the memory? just because hardware are better, doesn't mean we shouldn't care... just take a look at android world and you see how many application and service running, and some wrote by newbies, cause phone to crash...

Mister Jojo · Accepted Answer · 2022-09-08 13:59:37Z

1

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.

edited Sep 8, 2022 at 13:59

Mister Jojo

22.9k6 gold badges28 silver badges45 bronze badges

answered May 12, 2019 at 19:10

Nir M.

1591 silver badge5 bronze badges

1 Comment

Mister Jojo Over a year ago

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.

Will Ness · Accepted Answer · 2023-06-06 12:21:36Z

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.

Collectives™ on Stack Overflow

Quicksort: Iterative or Recursive

4 Answers 4

8 Comments

5 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

8 Comments

5 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related