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

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
using namespace std;
#include
#include
#include
#include

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; i0; 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.

darylesha

Newbie Poster

4 posts since Apr 2006

Reputation Points: 10

Solved Threads: 0

6 Years Ago

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

iamthwee

Posting Expert

5,950 posts since Aug 2005

Reputation Points: 1,543