Iterative Quicksort Illustration Inward Coffee - Without Recursion

The quicksort algorithm is i of the of import sorting algorithms. Similar to merge sort, quicksort too uses divide-and-conquer thence it's piece of cake to implement quicksort algorithm using recursion inward Java, but it's slightly to a greater extent than hard to write an iterative version of quicksort. That's why Interviewers are immediately quest to implement QuickSort without using recursion. The interview volition firstly alongside something similar writing a programme to form an array using quicksort algorithm inward Java as well as most probable you lot volition come upwards up alongside a recursive implementation of quicksort equally shown here. As a  follow-up, Interviewer volition immediately inquire you lot to code the same algorithm using Iteration.

If you lot remember, spell solving binary tree problems without recursion e.g. pre-order traversal without recursion (here) as well as in-order traversal without recursion (here), nosotros convey used Stack to supplant recursion. You tin role the same technique hither to write an iterative quicksort programme inward Java. The Stack truly mimics the recursion.

Iterative Quicksort Algorithm

I learned virtually quicksort inward my technology scientific discipline classes, i of the few algorithm which I managed to empathise then. Since it's a divide-and-conquer algorithm, you lot conduct a pin as well as split upwards the array. Unlike merge sort, which is too a divide-and-conquer algorithm as well as where all of import operate happens on combine steps, In quicksort, the existent operate happens inward split upwards measuring as well as the combining measuring does goose egg important.

Btw, the working of the algorithm volition rest same whether you lot implement an iterative solution or a recursion solution. In iterative solution, we'll role Stack instead of recursion. Here are the steps to implement iterative quicksort inward Java:

• Push the gain (0...n) into the Stack
• Partition the given array alongside a pivot
• Pop the endure past times element.
• Push the partitions ( index gain ) into a stack if the gain has to a greater extent than than i element
• Do the to a higher house three steps, till the stack, is empty

You mightiness know that fifty-fifty though writing recursive algorithms are piece of cake they are ever slower than their Iterative counterpart. So, when Interviewer volition inquire you lot to conduct a method inward price of  time complexity where retention is non a concern, which version volition you lot choose?

Well, both recursive as well as iterative quicksorts are O(N log N) average instance as well as O(n^2) inward the worst instance but the recursive version is shorter as well as clearer. Iterative is faster as well as makes you lot copy the recursion telephone band stack.

Btw, if you lot desire to empathise more about what does recursion convey to practice alongside the stack? as well as why does quicksort run inward O(n log n) fourth dimension inward the average case? I advise reading Grokking Algorithms, a rare algorithm majority which is piece of cake to empathise alongside existent Blue Planet examples. I only bought a re-create of this majority as well as fifty-fifty though I know all those algorithms, I notice it quite readable as well as gain a novel perspective. So, if you lot are struggling alongside the algorithms, this is the majority you lot should read now.

QuickSort instance inward Java without recursion.

Here is our sample Java programme to implement Quicksort using for loop as well as stack, without using recursion. This is too known equally iterative quicksort algorithm.

import java.util.Arrays; import java.util.Scanner; import java.util.Stack;  /**  * Java Program to implement Iterative QuickSort Algorithm, without recursion.  *  * @author WINDOWS 8  */ public class Sorting {      public static void main(String args[]) {          int[] unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};         System.out.println("Unsorted array : " + Arrays.toString(unsorted));          iterativeQsort(unsorted);         System.out.println("Sorted array : " + Arrays.toString(unsorted));     }       /*      * iterative implementation of quicksort sorting algorithm.      */     public static void iterativeQsort(int[] numbers) {         Stack stack = new Stack();         stack.push(0);         stack.push(numbers.length);          while (!stack.isEmpty()) {             int goal = stack.pop();             int firstly = stack.pop();             if (end - firstly < 2) {                 continue;             }             int p = firstly + ((end - start) / 2);             p = partition(numbers, p, start, end);              stack.push(p + 1);             stack.push(end);              stack.push(start);             stack.push(p);          }     }      /*      * Utility method to sectionalization the array into smaller array, as well as      * comparison numbers to rearrange them equally per quicksort algorithm.      */     private static int partition(int[] input, int position, int start, int end) {         int l = start;         int h = goal - 2;         int piv = input[position];         swap(input, position, goal - 1);          while (l < h) {             if (input[l] < piv) {                 l++;             } else if (input[h] >= piv) {                 h--;             } else {                 swap(input, l, h);             }         }         int idx = h;         if (input[h] < piv) {             idx++;         }         swap(input, goal - 1, idx);         return idx;     }      /**      * Utility method to swap 2 numbers inward given array      *      * @param arr - array on which swap volition occur      * @param i      * @param j      */     private static void swap(int[] arr, int i, int j) {         int temp = arr[i];         arr[i] = arr[j];         arr[j] = temp;     }  }  Output: Unsorted array : [34, 32, 43, 12, 11, 32, 22, 21, 32] Sorted array : [11, 12, 21, 22, 32, 32, 32, 34, 43]

That's all virtually how to implement quicksort inward Java without recursion. Just remember, when you lot role for loop as well as stack to implement quicksort, it's known equally iterative implementation as well as when you lot telephone band the method itself, it's known equally recursive implementation. The recursive solution of quicksort is easier to write as well as empathise but the iterative solution is much faster. Though average as well as worst instance fourth dimension complexity of both recursive as well as iterative quicksorts are O(N log N) average instance as well as O(n^2).

Btw, if you lot desire to holler back or review the fourth dimension complexity of dissimilar sorting algorithms e.g. quicksort, merge sort, insertion sort, radix sort, musical rhythm out sort, or bubble sort, hither is a overnice slide you lot tin impress as well as use:

If you lot desire to acquire to a greater extent than virtually quicksort or other sorting algorithms, I advise you lot either read tried as well as tested Introduction to Algorithms past times Thomas H. Cormen, which myself as well as several other programmers convey read to acquire fundamentals of information construction as well as algorithm. Alternatively, you lot tin too conduct the newer, but to a greater extent than interesting majority Grokking Algorithms past times Aditya Bhargava, who explains algorithms alongside lots of existent Blue Planet instance as well as diagrams. If you lot are a beginner, I would advise going for Grokking Algorithms.

Other data construction as well as algorithm articles you lot may like

• How to implement insertion form algorithm inward Java? (answer)
• Write a programme to implement bubble form inward Java? (solution)
• How to implement binary search algorithm inward Java? (solution)
• How to implement sieve of Eratosthenes algorithm inward Java? (solution)
• How to implement pre-order traversal of a binary tree inward Java? (solution)
• How to implement in-order traversal inward Java? (solution)
• How to impress all leafage nodes of a binary tree inward Java? (solution)
• How to implement binary search tree inward Java? (solution)

Further Learning
Data Structures as well as Algorithms: Deep Dive Using Java
Algorithms as well as Data Structures - Part 1 as well as 2
Data Structures inward Java ix past times Heinz Kabutz

Share this post