DaniWeb Forum Index > Software Development > C++

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

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Apr 2006

Posts: 4

Reputation: darylesha is an unknown quantity at this point

Solved Threads: 0

darylesha

Offline

Newbie Poster

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

Apr 5th, 2006

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.

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

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

Apr 5th, 2006

hmmm,

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

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

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
/**
 * 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;
}
/**
 * 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;
}