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.

hmmm,

``````/**
* 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;
}``````

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

****[/edit]

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.