Iterative Quick sort

I am not going to state basic Quick sort algorithm or its implementation. We all know about these stuffs. Today I am going to focus on Iterative Quick sort implementation in C. We know that Quick sort is recursive in nature. So we need a stack data structure. For that purpose we may use recursive function or use an external stack data structure to simulate recursive functions.  Throughout the post I am going to use the leftmost element as the pivot element and we are only concerned about array implementation. 
As it is an iterative code it will not have recursive calls to itself . We will use the external stack to hold the required data to operate on the array. We will iterate a loop until the external stack is empty . Every iteration of the loop will signify a recursive function execution. At each iteration we need to provide the limits ( lower and upper bound ) on which range Quick sort will operate. Now Array is same so we need not to worry about the array, only we need to worry about the limits. For that purpose we will use a structure that will hold both the lower and upper limit. Structure look like:

 
typedef struct activation
{
   int low;
   int up;
}boundary_t;

We will get the arguments (lower and upper  bound) for quick sort from the external stack and for that we have to push them first. Now we know that we will operate on the full array for the first time so we will push the structure containing low=0 and up=N-1 before calling Quick sort function. When the Quick sort will be executed, first it will pop the same structure and will operate on the given limit i.e low=0 and up=N-1. And then we will continue pushing signature of the Quick sort function according to partition and popping when we are going to operate on a new limit.

We can code the iterative version of Quick sort directly from its recursive version just by some modification. We need two modification. First modification is to place a push statement wherever a call to quick sort is and it will push the arguments (mainly lower and upper bound of the array ) of function call. Second is place a pop statement that will pop the required argument to work on the function at  the beginning of the Quick sort function and of-course termination checking criteria will change in recursive version it was checking whether the lower bound id smaller than the upper bound or not but in iterative version it will be checking stack's emptiness. If the stack is empty then stop.
This will look like this:-

+-----------------------------------+
|     Recursive version:            |
+-----------------------------------+
main()
 {
    .......
    .......
    *QS(arr[0:n-1])
    .......
    .......
 }

#QS (arr[ low:up ])
 {
    .......
    .......
    @ QS(arr[low:mid-1])
    $ QS(arr[mid+1:up])
 }


+-----------------------------------+
|     Iterative version:            |
+-----------------------------------+

main()
{
  ......
  ......
  * push(array[0:n-1]);
  ......
  ......
}

QS()
 {
     .....
     # args=pop()
     low=args.low
     up=args.up
     arr=args.array
     .......
     .......
     @ push(arr[low:mid-1])
     $ push(arr[mid+1:up])

 }

[ special characters used for mapping to recursive to iterative version]

Here is the C-code for the program:-

/* File containing the data to be sorted stored in space separated format and name of output 

file will be provided as command line argument */

#include<stdio .h>
#include<stdlib .h>
#define MAX_BUF 100000

typedef struct items
{
  int low;
  int up;
}item_t;

typedef struct stack
{
  item_t *arr;
  int top;
}stk_t;

stk_t *get_stack();
void push(stk_t *stk,item_t *item);
item_t pop(stk_t *stk);
void quick_sort(item_t item,int *arr);

int main(int argc,char **argv)
{
  int i,*arr,size;
  FILE *fp,*ft;
  item_t item;
  if(argc!=3)
  {
    printf("Wrong number of arguments!!\nExiting!!\n");
    exit(0);
  }
  fp=fopen(argv[1],"r");
  ft=fopen(argv[2],"w");
  fseek(ft,0,SEEK_SET);
  if(fp==NULL || ft==NULL)
  {
    printf("Error in openning file!!\n");
    exit(0);
  }
  fscanf(fp,"%d",&size);
  arr=malloc(sizeof(int)*size);
  for(i=0;iarr=malloc(sizeof(item_t)*(MAX_BUF+1));
  stk->top=-1;
  return stk;
}

void push(stk_t *stk,item_t *item)
{
  char ch;
 if(stk->toparr[++stk->top]=*item;
  }
 else
  {
    printf("Stack outof memory!!\n");  
    exit(0);
  }
}

item_t pop(stk_t *stk)
{
  item_t empty;
  if(stk->top>-1)
   {
     return (stk->arr[stk->top--]);
   }
  else
   {
     empty.low=-1;
     empty.up=-1;
     printf("Stack is empty!!\n");
     return empty;
   }
}

void quick_sort(item_t item,int *arr)
{
  int pivot,i,j,temp;
  item_t *item_1,*item_2,*t_item;
  stk_t *stk;
  item_1=malloc(sizeof(item_t));
  item_2=malloc(sizeof(item_t));  
  stk=get_stack();
  t_item=&item;
  push(stk,t_item);
  while(1)
  {
    item=pop(stk);
    if(item.low==-1 && item.up==-1)
      break;
    if(item.lowpivot);
  if(ilow=item.low;
      item_1->up=j-1;
      item_2->low=j+1;
      item_2->up=item.up;
      push(stk,item_1);
      push(stk,item_2);
    }
  }
}