Shell Sort w/ fibonacci numbers...HELP!!! Due Friday

[darylesha]

Hey ya'll, I am working on this assignment that has me that is as follows:

/*
 Modify the following shell sort to use the fibonacci sequence, instead of 
the sequence h = 3h+1.

Hint use dynamic programming to do this.


*/

#include <iostream>
using namespace std;
#include <stdlib.h>
#include <fstream>
#include <string>
#include <time.h>

long comparisons = 0;
long exchanges = 0;
ofstream fout("output.txt");

void ran(int a[], int N)
{
    int i;
    srand((unsigned)time(NULL));  //Give us a random array that will be fixed for all sorts
    for(i = 0; i<N; i++)
        a[i] = int(1000*(1.0*rand()/RAND_MAX));
}

void initial(int a[], int b[], int N)
{
    int i;
    for(i =0 ; i < N; i++) a[i] = b[i];
}

void output( int a[], int l, int r)
{
    int i;
    for( i = l; i <= r; i++) fout << a[i] << " ";
    fout << endl;
}
void shellsort(int a[], int l, int r)
{
    int i,j,h, v;
//  for(h = 1; h <= (r)/9; h = 3*h+1);
//  for( ; h>0; h/=3)
//      for(i = l+h; i <= r; i++)
        {
            j =i;
            v = a[i];
            while(j >= l+h && v < a[j-h])
            {
                a[j] = a[j-h];
                j -= h;
            }
            a[j] = v;
        }

}
int main(int argc, char *argv[])
{
    int i, N = atoi(argv[1]), sw = atoi(argv[2]);
    int *a = new int[N], *b = new int[N];
    string filename;
    int choice = 0;
    if(sw)
        ran(a, N);
    else
    {
        cout << "enter file name" << endl;
        cin >> filename;
        ifstream fin(filename.c_str());
        for(i = 0; i < N; i++) fin >> a[i];
    }
    for( i = 0; i < N; i++)
    {
         fout << a[i] << " ";
    }
    fout << endl;
    shellsort(a, 0 , N-1); 
    fout << "Shell Sort " << endl; 
    output(a, 0, N-1);
    return 0;
}

Any Help would be greatly appreciated. I know how the fibonacci sequence works, but I do not know how to add it to this program.

[iamthwee]

hmmm,

Perhaps this link may answer your question. Not sure though.

http://www.answers.com/topic/shell-sort

/**
 * Performs an insertion sort on elements of a[] with the given gap.
 * If gap == 1, performs an ordinary insertion sort.
 * If gap >= length, does nothing.
 * Based on a C implementation from the article Insertion sort implementations
 */
#include <iostream>
using namespace std;

void shellSortPhase(int a[], size_t length, size_t gap) {
    int i;

    for (i = gap; i < length; ++i) {
        int value = a[i];
        int j;
        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
            a[j + gap] = a[j];
        }
        a[j + gap] = value;
    }
}

void shellSort(int a[], size_t length) {
    /*
     * gaps[] should approximate a geometric progression.
     * The following gaps are every other Fibonacci number,
     * which gives r=2.616.
     */
    static const int gaps[] = {
        1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946
    };
    int sizeIndex;

    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
               sizeIndex >= 0;
               --sizeIndex)
        shellSortPhase(a, length, gaps[sizeIndex]);
}
int main()
{
    int a[] = {7,34,6,3,2,7,8,12,3,5};
    
    shellSort(a,10);
    for(int i=0; i<10; i++)
    {
        cout<<a[i]<<" ";
    }    
    cin.get();
    return 0;
}

[darylesha]

I'm not fully understanding what that program does. If u could try to explain it to me, it would be greatly appreciated.

[SpS]

[edit]****[/edit]