recursion to iteration

[now how abt tht]

I have the following code for shell sort (recursive) given in the question
where t[ ] is an array to be sorted, n=no of elements initially. h is any large no initially,say h>n.

void shell_rec(int t[],int n,int h)
{
	int aux,i;
	if(h<=0)
	return;
	
	if(n>h)
	{	shell_rec(t,n-h,h);
		if(t[n]<t[n-h])
		{
			aux=t[n];
			i=n;
		       for(i=n;i>=h && aux<t[i-h];i=i-h)
				t[i]=t[i-h];
			t[i]=aux;
		}
	}
	
	shell_rec(t,n,h/3);
}

removing tail recursion i get:

void shell_rec(int t[],int n,int h)
{
	int aux,i;
	int j;
	for(j=h;j>0;j=j/3)
	{	
	if(n>j)
	{	shell_rec(t,n-j,j);
		if(t[n]<t[n-j])
		{
			aux=t[n];
			i=n;
		       for(i=n;i>=j && aux<t[i-j];i=i-j)
				t[i]=t[i-j];
			t[i]=aux;
		}
	}
	}	
}

now i want to remove the recursion using explicit stack
pls help!

[Schol-R-LEA]

What aspect of it do you need help with?

[now how abt tht]

remove the recursive call assuming stack operations push pop etc are given
I dont know how to deal with the for loop here

[Narue]

I dont know how to deal with the for loop here

So don't deal with it. The simplest way to turn recursion into iteration is by expanding the recursion literally using stacks and unconditional jumps. For example:

void shell_rec(int t[], int n, int h)
{
    int stack_n[50];
    int stack_h[50];
    int stack_call[50];
    int top = 0;
    int tempn, temph;
    
    stack_n[top] = n;
    stack_h[top] = h;
    ++top;
    
recursion_start:
    tempn = stack_n[top - 1];
    temph = stack_h[top - 1];
    
    if (temph <= 0)
        goto recursion_return;
        
    if (tempn > temph) {
        //shell_rec(t, n - h, h);
        stack_call[top] = 1;
        stack_n[top] = tempn - temph;
        stack_h[top] = temph;
        ++top;
        goto recursion_start;
        
first_recursive_call:
        tempn = stack_n[top - 1];
        temph = stack_h[top - 1];
        
        if (t[tempn] < t[tempn - temph]) {
            int aux = t[tempn];
            int i;
            
            for (i = tempn; i >= temph && aux < t[i - temph]; i = i - temph)
            {
                t[i] = t[i - temph];
            }
            
            t[i] = aux;
        }
    }

    //shell_rec(t, n, h / 3);
    stack_call[top] = 2;
    stack_n[top] = tempn;
    stack_h[top] = temph / 3;
    ++top;
    goto recursion_start;
    
second_recursive_call:
    goto recursion_return;
    
recursion_return:
    if (top == 0)
        return;
    
    if (stack_call[--top] == 1)
        goto first_recursive_call;
    else
        goto second_recursive_call;
}

From there you can clean up to gotos into loops, and relationships that can be compacted are easier to see because the flow of control and which pieces of changing information are explicit.

[now how abt tht]

thank you Narue!!
you are a true code goddess!! \m/

[now how abt tht]

this prob in no way can be done w/o stack_call[ ] right?
i mean we will always need an extra variable in the stack to indicate which recursion it is.

so the algo:
#include "StackOps.h"
#include "SortOps.h"

void shell_iter(int *t,int n, int h)
{
  int i,aux;
  Stack stack;
  Stack *stackp;
  stackp=&stack;
  stack=createStack(stack);
  while(h>0)
  {
         while(n>h){
            stack=push(stack,n);
            n=n-h;
            }
         while(!isEmpty(stackp))
    {
            n=pop(stackp);
               if (t[n]<t[n-h])
            {
               aux=t[n];
               i=n;
               while (i>=h && aux<t[i-h]){
                  t[i]=t[i-h];
                  i=i-h;
               }
               t[i]=aux;
            }
         }
     h=h/3;
     }
}

is flawed right?
this algo does not wrk i suppose. please confirm and let me know.

[Adak]

Shell sort is Insertion sort, with an added outer loop that allows values to be moved a longer distance, in one loop, when it's advantageous.

As the gap in the outer loop is reduced, Shell sort becomes more and more like Insertion sort. In it's last time through it's inner loop, it is identical to Insertion sort.

Insertion sort is known to be a very efficient sort, on small to medium sized arrays, especially when the data is in almost sorted order. It makes an excellent optimization for Quicksort, when the sub arrays have less than 50 numbers in them.

This is Insertion sort:

void insertionSort(int a[], int lo, int hi) {
   int i, j, val; 
   for(i=lo+1;i<hi;i++) {  
      val = a[i];
      j = i-1;
      while(a[j] > val) {
         a[j + 1] = a[j];
         --j;
         if(j<0) break;
      }   
      a[j+1] = val;
   }
}

And here is an iterative Shell sort:

//Shell sort
void shellSort(int a[], int hi) {
  int i, j, gap, temp;

   for(gap = hi/2; gap > 0; gap /= 2) {
      for(i = gap; i < hi; i++) {            //Insertion sort starts here
         temp = a[i];
         j = i;
         while(j>= gap && a[j-gap] > temp) {
            a[j] = a[j - gap];
            j = j - gap;
         }
         a[j] = temp;                        //and ends here
      }
   }
}

This is the results of a sorting program I ran recently, with several sorting algorithms. First, a medium sized integer array of random numbers was sorted, and then a larger 100,000 array of random integers was sorted. Although there are better gap increments than was used here, (this was the original scheme of Dr. Shell), still, Shell sort did a fine job.

Times listed are only sorting time, and only CPU seconds, not wall time, in a single thread. In each test, 50.04% of the numbers are not in sorted order, as the sorting begins.

This is the first run, SIZE is 10,000:

Start Sorting Test Run
========================

Bubble sort               0.156
 Insertion sort            0.016
 Quicksort, unoptimized    0.000
 Quicksort, optimized      0.000
 Shell Sort, unoptimized   0.015
 Substitution sort         0.156

Second run, SIZE is 100,000:

Start Sorting Test Run
========================

Bubble sort              15.023
 Insertion sort            2.153
 Quicksort, unoptimized    0.016
 Quicksort, optimized      0.000
 Shell Sort, unoptimized   0.015
 Substitution sort        16.068

Bubble and Substitution sort handled the first test of 10,000 numbers, in less than 1/5th of a second - impressive! Then they were overwhelmed by the sheer volume of numbers in the second test. Had to happen, sooner or later.

Insertion sort was able to almost match Shell sort, (which is an optimization of Insertion sort), in the first test. Shell's sort, proved it's worth in the larger second test, even beating unoptimized Quicksort, by a tick. Both were 9.75 times faster than Bubble or Substitution sort, in the first test.

When the data set is large, and the values are highly mixed, Quicksort really comes into it's own, and Shell sort came right along with it. The optimized Quicksort version used Insertion sort for finishing off partly sorted sub arrays with less than 50 numbers. This is a fine optimization for Quicksort, as that 0.000 timer, clearly shows.